题目描述

题目链接：155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

例子

例子 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

Output: [null,null,null,null,-3,null,0,-2] Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints

• -2^31 <= val <= 2^31 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

解题思路

要求实现一个栈，除了包含常规栈的功能外还能维护并返回当前栈中的最小值。思路比较简单，除了用一个数组实现常规栈的功能以外，再用一个数组来维护当前栈中的最小值即可，维护的方法是每当压入一个值判断其是否比当前最小值数组最末尾的元素小，如果小则表示找到了一个新的最小值，将其压入数组中。返回时只需要返回最小值栈末尾元素即可；同时栈弹出时也要判断栈顶元素是否为最小值数组末尾元素，如果是则表示该值要被弹出。代码如下：

#include <vector>

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {}

    void push(int val) {
        all_.push_back(val);
        if (min_.empty() || min_.back() >= val) {
            min_.push_back(val);
        }
    }

    void pop() {
        int val = all_.back();
        if (val == min_.back()) min_.pop_back();
        all_.pop_back();
    }

    int top() { return all_.back(); }

    int getMin() { return min_.back(); }

private:
    std::vector<int> min_;
    std::vector<int> all_;
};

• 时间复杂度:O(1)
• 空间复杂度:O(n)

GitHub 代码同步地址： 155.MinStack.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions