包含min函数的栈(Hulu面试题)

题目链接

另外开一个单调栈(stk_min)表示前i个元素中的最小值

• 如何维护stk_min这个栈？

•    每次push_back(min(stk_min.top(), x))
     每次pop_back(stk_min.top()) 
  

参考代码

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk, stk_min;
    
    MinStack() {
        
    }
    
    void push(int x) {
        stk.push(x);
        if (stk_min.size()) x= min(x, stk_min.top());
        stk_min.push(x);
    }
    
    void pop() {
        stk.pop();
        stk_min.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return stk_min.top();
    }
};