包含min函数的栈(剑指Offer-30)

题面

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例

1MinStack minStack = new MinStack();
2minStack.push(-2);
3minStack.push(0);
4minStack.push(-3);
5minStack.min();   --> 返回 -3.
6minStack.pop();
7minStack.top();      --> 返回 0.
8minStack.min();   --> 返回 -2.

限制

1各函数的调用总次数不超过 20000 次

思路

除了常规的栈，再维护一个单调栈，从栈顶到栈底递增

常规栈常规添加删除元素

单调栈栈顶元素大于等于待加入元素或者单调栈为空，则入栈；当常规栈的出栈元素等于单调栈的栈顶元素，单调栈出栈

代码

 1class MinStack {
 2    stack<int> s, t;
 3public:
 4    /** initialize your data structure here. */
 5    MinStack() {
 6
 7    }
 8
 9    void push(int x) {
10        if(t.empty() || t.top() >= x)
11            t.push(x);
12        s.push(x);
13    }
14
15    void pop() {
16        if(t.top() == s.top())
17            t.pop();
18        s.pop();
19    }
20
21    int top() {
22        return s.top();
23    }
24
25    int min() {
26        return t.top();
27    }
28};
29
30/**
31 * Your MinStack object will be instantiated and called as such:
32 * MinStack* obj = new MinStack();
33 * obj->push(x);
34 * obj->pop();
35 * int param_3 = obj->top();
36 * int param_4 = obj->min();
37 */