【LeetCode】-- 15.最小栈

1. 题目

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

实现 MinStack 类:

       MinStack() 初始化堆栈对象。

       void push(int val) 将元素val推入堆栈。

       void pop() 删除堆栈顶部的元素。

       int top() 获取堆栈顶部的元素。

       int getMin() 获取堆栈中的最小元素。

2. 示例

输入：

       ["MinStack","push","push","push","getMin","pop","top","getMin"]

       [[],[-2],[0],[-3],[],[],[],[]]

输出：

       [null,null,null,null,-3,null,0,-2]

解释：

       MinStack minStack = new MinStack();

       minStack.push(-2);

       minStack.push(0);

       minStack.push(-3);

       minStack.getMin();   --> 返回 -3.

       minStack.pop();

       minStack.top();      --> 返回 0.

       minStack.getMin();   --> 返回 -2.

3. 分析

（1）常数时间要求时间复杂度为O(1)

（2）MinStack、push、pop、top都比较简单，主要分析getMin：

        如果用一个变量记录最小值，每入栈一个元素就更新最小值，时间复杂度为O(1)。

       那么每出栈一个元素也要更新最小值，如果出栈的元素不是最小值，那么最小值不用更新；

       如果出栈的元素是最小值，那么要在留在栈里的元素中找到最小值就只能遍历整个栈了，时间复杂度为O(N)，不符合题目要求，所以记录最小值的方法是行不通的。

       

       为了删除一个元素后，最小值能被记录下来，可以考虑用两个栈，栈2保留栈1的最小值，当栈1元素出栈时，栈2中保留有栈1出栈后的最小值，不需要遍历栈1找最小值了，用空间换时间的思想来解决了问题。

stack1删除元素时，删除top元素1，栈中元素为8 5 3 9 2 6，stack1中最小值为stack2中删除top元素1之后的top元素2

4. 代码实现

1. class MinStack {
2. public:
3. //构造函数使用栈的默认构造函数即可
4. MinStack() {
5. 
6.     }
7. 
8. void push(int val) {
9.       _st.push(val);
10. 
11. //当_st入栈时，如果入栈元素<_minst的栈顶元素，那么_minst也需入栈
12. if(_minst.empty() || val <= _minst.top())
13.       {
14.           _minst.push(val);
15.       }
16. 
17.     }
18. 
19. void pop() {
20. 
21. //两个栈顶元素如果相等，_minst才需要出栈
22. if(_st.top() == _minst.top())
23.         {
24.             _minst.pop();
25.         }
26.         _st.pop();
27.     }
28. 
29. int top() {
30. return _st.top();
31.     }
32. 
33. int getMin() {
34. return _minst.top();
35.     }
36. 
37. private:  
38.     stack<int> _st;
39.     stack<int> _minst;
40. 
41. };