操作一:返回栈顶元素
操作二:将value加入push到栈顶
操作三:将栈顶元素删除
操作四:返回栈里面最小的一个元素
操作一,二,三是栈stack的基本操作;
如果用O(1)的时间复杂度直接返回栈里面最小的元素呢?
用第二个栈来维护第一个栈里面的最小元素:sta1, sta2
当执行操作二时:只有当sta2为空或者valuesta2.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();
    }
};