描述

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

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例

  1. 输入：
  2. ["MinStack","push","push","push","getMin","pop","top","getMin"]
  3. [[],[-2],[0],[-3],[],[],[],[]]
  5. 输出：
  6. [null,null,null,null,-3,null,0,-2]
  8. 解释：
  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.

提示

  • pop、top 和 getMin 操作总是在 非空栈 上调用。

解题思路

思路

对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。

因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。

那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。

算法

按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

  • 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
  • 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
  • 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

代码

  1. class MinStack {
  2.     Deque<Integer> stack;
  3.     Deque<Integer> help;
  4.     public MinStack() {
  5.         stack = new LinkedList<>();
  6.         help = new LinkedList<>();
  7.         help.addLast(Integer.MAX_VALUE);
  8.     }
  10.     public void push(int val) {
  11.         stack.addLast(val);
  12.         help.addLast(Math.min(val, help.peekLast()));
  13.     }
  15.     public void pop() {
  16.         stack.pollLast();
  17.         help.pollLast();
  18.     }
  20.     public int top() {
  21.         return stack.peekLast();
  22.     }
  24.     public int getMin() {
  25.         return help.peekLast();
  26.     }
  27. }