c++刷剑指offer（面试题30. 包含min函数的栈）【栈】

糖逗

题目描述：

1. 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
   
2. 
   
3.  
   
4. 
   
5. 示例:
   
6. 
   
7. MinStack minStack = new MinStack();
   
8. minStack.push(-2);
   
9. minStack.push(0);
   
10. minStack.push(-3);
    
11. minStack.min();   --> 返回 -3.
    
12. minStack.pop();
    
13. minStack.top();      --> 返回 0.
    
14. minStack.min();   --> 返回 -2.
    
15.  
    
16. 
    
17. 提示：
    
18. 
    
19. 各函数的调用总次数不超过 20000 次
    
20.  
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <stack>
   
3. 
   
4. using namespace std;
   
5. 
   
6. 
   
7. class MinStack {
   
8. private:
   
9.     stack<int> temp1;
   
10.     stack<int> temp2;
    
11. public:
    
12.     /** initialize your data structure here. */
    
13.     MinStack() {
    
14. 
    
15.     }
    
16.    
    
17.     void push(int x) {
    
18.         temp1.push(x);
    
19.         if(temp2.empty() || temp2.top() >= x){
    
20.             temp2.push(x);
    
21.         }
    
22.     }
    
23.    
    
24.     void pop() {
    
25.         if(temp1.empty()) return;
    
26.         if(temp1.top() == temp2.top()) temp2.pop();
    
27.         temp1.pop();
    
28. 
    
29.     }
    
30.    
    
31.     int top() {
    
32.         return temp1.top();
    
33. 
    
34.     }
    
35.    
    
36.     int min() {
    
37.         return temp2.top();
    
38. 
    
39.     }
    
40. };
    
41. 
    
42. 
    
43. int main(void){
    
44.         MinStack temp;
    
45.         temp.push(2);
    
46.         temp.push(3);
    
47.         temp.push(1);
    
48.         cout << temp.min() << endl;
    
49.         cout << "----------" << endl;
    
50.         temp.pop();
    
51.         cout << temp.min() << endl;
    
52.         cout << "----------" << endl;       
    
53.         return 0;
    
54. }
    

复制代码

注意事项：
1.用temp2的顶端存储最小值。

糖逗

1. if(temp2.empty() || temp2.top() >= x)

复制代码

上面19行的代码一定要加上等号！！！！！！
因为，假如1是最小的数，且有2个1，从栈中去除1个1，当前最小值还是1。

糖逗