网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的155. 最小栈，难度为 Easy。
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
示例:
输入： ["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. 复制代码
提示：
- pop、top 和 getMin 操作总是在「非空栈」上调用。
双栈解法
为了快速找到栈中最小的元素，我们可以使用一个辅助栈 help。
通过控制 help 的压栈逻辑来实现：help 栈顶中始终存放着栈内元素的最小值。
网络异常，图片无法展示
|
代码：
class MinStack { Deque<Integer> data = new ArrayDeque<>(); Deque<Integer> help = new ArrayDeque<>(); public void push(int val) { data.addLast(val); if (help.isEmpty() || help.peekLast() >= val) { help.addLast(val); } else { help.addLast(help.peekLast()); } } public void pop() { data.pollLast(); help.pollLast(); } public int top() { return data.peekLast(); } public int getMin() { return help.peekLast(); } } 复制代码
- 时间复杂度：所有的操作均为 O(1)O(1)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.155 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
