【题解】剑指Offer-30 包含min函数的栈

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

题面

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

示例

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

限制

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

思路

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

常规栈常规添加删除元素

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MinStack {
stack<int> s, t;
public:
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
if(t.empty() || t.top() >= x)
t.push(x);
s.push(x);
}

void pop() {
if(t.top() == s.top())
t.pop();
s.pop();
}

int top() {
return s.top();
}

int min() {
return t.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/