大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“实现MinStack类，实现push/pop/top操作。”
2、题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例 1： 输入： ["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.
示例 2：
二、解题
1、思路分析
这道题是实现MinStack类，实现push/pop/top操作。
要解决这道题，首先需要了解的是栈的性质。
栈结构是先进后出的结构，当一个元素入栈时，栈内的其他元素一定还在栈内。
直到栈内的其他元素弹出后，新元素才能出栈。
那么就可以在每个元素入栈的时候，保存栈内最小值，那么无论何时，栈顶元素都是存储的最小值。
2、代码实现
代码参考：
class MinStack { Deque<Integer> xStack; Deque<Integer> minStack; public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } }
3、时间复杂度
时间复杂度：O(1)
因为栈的插入、删除和读取的操作都是O(1)。
空间复杂度：O(n)
其中n是总操作数，在最坏情况下，会连续插入n个元素。
三、总结
用一个栈，这个栈同时保存的是每个数字进栈的时候的值 与 插入该值后的栈内最小值。
即每次新元素入栈的时候保存一个元组： （当前值 ，栈内最小值） 。
