LeetCode 最小栈

题目链接：https://leetcode-cn.com/problems/min-stack/

题目大意

　　略。并且题目中要求的操作都要 O(1) 实现。

分析

　　用 2 个栈，一个普通栈，一个单调栈。

代码如下

 1 class MinStack {
 2 public:
 3     /** initialize your data structure here. */
 4     stack< int > sk;
 5     stack< int > minsk; // 从栈底到栈顶递增的单调栈
 6     
 7     MinStack() {
 8         
 9     }
10     
11     void push(int x) {
12         sk.push(x);
13         if(!minsk.empty() && x > minsk.top()) minsk.push(minsk.top());
14         else minsk.push(x);
15     }
16     
17     void pop() {
18         //assert(!sk.empty() && !minsk.empty());
19         sk.pop();
20         minsk.pop();
21     }
22     
23     int top() {
24         //assert(!sk.empty());
25         return sk.top();
26     }
27     
28     int getMin() {
29         //assert(!minsk.empty());
30         return minsk.top();
31     }
32 };
33 
34 /**
35  * Your MinStack object will be instantiated and called as such:
36  * MinStack* obj = new MinStack();
37  * obj->push(x);
38  * obj->pop();
39  * int param_3 = obj->top();
40  * int param_4 = obj->getMin();
41  */

View Code