leetcode155. 最小栈

一、题目描述：

   计划一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
  实现 MinStack 类:
  

• MinStack() 初始化堆栈对象。
  
• void push(int val) 将元素val推入堆栈。
  
• void pop() 删除堆栈顶部的元素。
  
• int top() 获取堆栈顶部的元素。
  
• int getMin() 获取堆栈中的最小元素。
  

  二、输入输出实例：

  

1. <strong>输入：</strong>
2. ["MinStack","push","push","push","getMin","pop","top","getMin"]
3. [[],[-2],[0],[-3],[],[],[],[]]
5. <strong>输出：</strong>
6. [null,null,null,null,-3,null,0,-2]
8. <strong>解释：</strong>
9. MinStack minStack = new MinStack();
10. minStack.push(-2);
11. minStack.push(0);
12. minStack.push(-3);
13. minStack.getMin();   --> 返回 -3.
14. minStack.pop();
15. minStack.top();      --> 返回 0.
16. minStack.getMin();   --> 返回 -2.

复制代码

三、思绪解说：

   

• 创建两个stack对象，stack1用来存储入栈元素，stack2用来存储栈当前最小元素。
  
• push函数思绪：
  

          ①无论什么环境stack1都必要压栈。
          ②当stack2为空，或者stack2栈顶的元素和当前必要压栈的元素相等时，stack2执行压         栈操作。
  

• pop函数思绪：
  

          ①无论什么环境stack1都必要出栈。
          ②当stack2栈顶元素和stack1栈顶元素相等时，stack2执行出栈。
          ③当stack2不和stack1栈顶元素相等，分析要出栈的元素不是stack1栈中当前最小元素 
          那么这个元素可以直接弹出。
  

• 构造函数可以删掉，删掉后编译器会生成默认构造函数；不删掉也可以不用剖析，由于这个类只有内置类型，所有内置类型都会自己走初始化列表。
  
• top函数返回stack1的栈顶元素即可。
  
• getMin返回stack2栈顶元素即可，stack2栈顶元素是当前栈中最小的元素。
  

  四、C++代码：

  

1. class MinStack {
2.     stack<int> s1;
3.     stack<int> s2;
4. public:
5.     MinStack()
6.     {
7.         //不用写，内置类型会自己走初始化列表
8.     }
9.    
10.     void push(int val)
11.     {
12.         s1.push(val);//主栈压栈
13.         if(s2.empty()||val<=s2.top())//辅栈如果为空，或者val小于辅栈栈顶元素
14.                                      //辅栈压栈
15.         {
16.             s2.push(val);
17.         }
18.     }
19.    
20.     void pop()
21.     {
22.         if(s1.top()==s2.top())//如果主栈和辅栈的栈顶元素大小相等
23.                               //辅栈出栈
24.         {
25.             s2.pop();
26.         }
27.         s1.pop();//主栈无论如何都出栈
28.     }
29.    
30.     int top()//返回主栈的栈顶位置元素
31.     {
32.         return s1.top();
33.     }
34.    
35.     int getMin()//返回辅栈的栈顶元素，也就是主栈最小元素
36.     {
37.         return s2.top();
38.     }
39. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。