题解 | #自动管理停车场桩位系统#
自动管理停车场桩位系统
http://www.nowcoder.com/questionTerminal/4c7f2556e7e8436189202942b4fa07e4
操作一：返回栈顶元素
操作二：将value加入push到栈顶
操作三：将栈顶元素删除
操作四：返回栈里面最小的一个元素
操作一,二,三是栈stack的基本操作;
如果用O(1)的时间复杂度直接返回栈里面最小的元素呢？
用第二个栈来维护第一个栈里面的最小元素：sta1, sta2
当执行操作二时：只有当sta2为空或者value
sta2.top()时,才将value加入到sta2的栈顶里,这样做：sta2里面只放入最小的元素(sta2里面的元素可能有多个,但栈顶一定是目前最小的元素)
只要最小的元素还在sta1里面,那么该最小元素就一定在sta2的栈顶
当执行操作三时：如果删除的sta1.top()正好是sta2.top()，那么需要将sta2.top()一同删除
总代码：
class Solution {
public:
stack<int> sta1, sta2;
void push(int value) {
sta1.push(value);
if(!sta2.size() || value < sta2.top()) sta2.push(value);
}
void pop() {
if(sta1.top() == sta2.top()) sta2.pop();
sta1.pop();
}
int top() {
return sta1.top();
}
int min() {
return sta2.top();
}
};
