【Leetcode】【Easy】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.

实现一个栈的基本功能，并且可以用o(1)的时间取出栈的最小元素。

使用两个栈的解题方法：

建立两个栈容器，一个常规使用elementStack，一个保存栈内最小元素minStack。

注意：

常规栈中最小的元素可能不唯一。当某个最小元素出栈时，minStack也需做出出栈动作。因此minStack栈中记录最小元素的数量应该和elementStack中最小元素数量相同。

也就是，每次进行常规栈压栈时，都进行和min栈记录的最小元素比较，将小于等于min栈最小元素的常规元素压栈。

代码：

 1 class MinStack {
 2 public:
 3     void push(int x) {
 4         element.push(x);
 5         if (min.empty() || x <= min.top()) 
 6             min.push(x);
 7     }
 8 
 9     void pop() {
10         if (!element.empty()) {
11             if (element.top() == min.top()) 
12                 min.pop();
13             element.pop();
14         }
15     }
16 
17     int top() {
18         if (!element.empty())
19             return element.top();
20     }
21 
22     int getMin() {
23         if (!min.empty())
24             return min.top();
25     }
26     
27 private:
28     stack<int> element;
29     stack<int> min;
30 };

也可以只使用一个栈，即常规栈。只是压栈的每个元素都包含当前栈内最小元素值。

即，假设当前栈内最小值为m，当对元素A压栈时，若A<=m，则压入 (A, A)，若A>m，则压入 (A, m)。

（代码略）

附录：

各种数据结构最简洁表示方法，参考《数据结构与算法分析—C语言版》