[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(); } };