LeetCode Min Stack

155. Min Stack

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

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

本题要实现一个最小栈,使得push, pop, top以及getMin都是以O(1)的时间完成。

这是一个非常经典的双栈法题目,我居然不知道。同时使用两个栈,一个普通的用于存放所有数据allStack,另一个只用于存储最小值序列minStack。 push的时候,每次都把x push进allStack。如果minStack为空,则是第一次push,要把x push进minStack;如果minStack非空,则当x小于等于minStack栈顶时,可以把x push进minStack。注意当x等于minStack栈顶的时候也是需要进栈的,因为有可能有重复元素,比如对0,1,0依次进栈,遇到后面的0时,minStack只有前一个0,此时如果后一个0不进栈,如果下一步是pop的话,就会把minStack中的上一个0 pop掉,那么此时getMin时就会出错,因为此时minStack里没东西了,但allStack还保留着0和1,正确的最小值应该是前一个0。 pop时,allStack正常pop。如果pop出来的值等于minStack的栈顶,则minStack也需要pop。 top就取allStack的top。 getMin就取minStack的top。 完整代码如下:

class MinStack {
private:
    stack<int> allStack, minStack;

public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty()) {
            minStack.push(x);
        }
        else if (x <= minStack.top()) { // 注意是<=而不是<
            minStack.push(x);
        }
        allStack.push(x);
    }
    void pop()
    {
        int top = allStack.top();
        allStack.pop();
        if (top == minStack.top()) {
            minStack.pop();
        }
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC,用时29MS。

二刷。其实可以更简单一点,辅助的minStack大小始终和allStack一样,当新入元素小于minStack栈顶元素时,自然入minStack;否则,就把minStack栈顶的元素再入一次栈。这样就使得两个栈的大小一样,pop的时候可以同时pop,减少了各种if判断。
完整代码如下:

class MinStack {
private:
    stack<int> allStack, minStack;
public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty() || x < minStack.top()) {
            minStack.push(x);
        }
        else {
            minStack.push(minStack.top());
        }
        allStack.push(x);
    }
    void pop()
    {
        allStack.pop();
        minStack.pop();
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC,用时29MS。

Leave a Reply

Your email address will not be published. Required fields are marked *