Tuesday, November 18, 2014

[LeetCode新题] 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.

思路:

看到题目第一反应是用一个int minVal来记录整个stack当前的最小值就可以了。然后仔细想下,发现问题在于当这个最小值被pop以后,无法O(1)时间得到新的最小值。所以问题的关键在于要跟踪记录每个新数字压入栈时的当前最小值,而不是只记录一个总的最小值。

一种思路是将make_pair(xi, curMin)一起压入栈stack<pair<int,int>>中。但这种方法的空间复杂度为2n。再仔细观察,发现只有当push或pop的对象xi<= min(stack)时,才会影响到min(stack)的值。

用另一个stack<int> trackMin来记录min值的变化,trackMin.top()表示当前最小值。
当有新的xi<=trackMin.top()被压入时,将xi压入trackMin变为新的当前最小值。
当xi==trackMin.top()时被pop出时,trackMin也同时pop。

这里的一个关键是理解为什么是x<=trackMin.top()而不是x<trackMin.top()。加入对于push(x)只有当x<trackMin.top()时,才将x压入trackMin中。

例如压入以下数后:
xi:    3 2 1 2 1 
trackMin: 3 2 1

此时如果pop,则变为
xi:    3 2 1 2
trackMin: 3 2

然而实际栈里的最小值仍旧为1,这个1因为重复数字的关系在trackMin中丢失。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MinStack {
    stack<int> s;
    stack<int> trackMin;
public:
    void push(int x) {
        if(trackMin.empty() || x<=trackMin.top())
            trackMin.push(x);
        s.push(x);
    }

    void pop() {
        if(s.empty()) return;
        if(s.top()==trackMin.top())
            trackMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return trackMin.top();
    }
};

6 comments:

  1. 例子中
    例如压入以下数后:
    xi: 3 2 1 2 1
    trackMin: 3 2 1

    trackMin 应该是3 2 1 1 吧

    ReplyDelete
    Replies
    1. 博主说的是“加入对于push(x)只有当x<trackMin.top()时,才将x压入trackMin中”,所以只有一个1在trackMin里

      Delete
  2. 有没有什么办法用一个栈就可以解决问题呢?

    ReplyDelete
    Replies
    1. 一个栈加 O(1) space 的算法:http://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

      Delete
    2. 这个算法有问题,*2 以后可能超边界

      Delete