题目

设计一个支持 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.

  2. <a name="7qy3t"></a>
  3. # 解题思路
  4. 采用一个 `List` 来实现栈，一个 `List` 来保存栈的信息：数据在栈中的位置，数据本身，栈的最小值对应的数据放在min末尾，如下图：-2，0，-3分别入栈后，min的变化<br />![Stack.png](https://cdn.nlark.com/yuque/0/2020/png/661000/1587993786294-e3a68804-9119-4779-b80f-7ae0db28b395.png#align=left&display=inline&height=405&margin=%5Bobject%20Object%5D&name=Stack.png&originHeight=405&originWidth=508&size=10752&status=done&style=none&width=508)
  6. 1. -2 入栈，-2在栈中的位置与值本身写入 `min` 中
  7. 1. 0 入栈，由于-2比0大，所以在栈中，-2最小，因此需要把{1，0}插入到{0，-2}前，保证 `min` 末尾存储栈的最小值信息
  8. 1. -3 入栈，由于-3是最小的，所以直接加在 `min` 末尾
  9. <a name="ppzGF"></a>
  10. # 代码
  11. ```java
  12. import java.util.ArrayList;
  13. import java.util.List;
  15. class MinStack {
  16.     private List<Integer> data;
  17.     private List<Node> min;
  19.     /**
  20.      * initialize your data structure here.
  21.      */
  22.     public MinStack() {
  23.         data = new ArrayList<>();
  24.         min = new ArrayList<>();
  25.     }
  27.     public void push(int x) {
  28.         data.add(x);
  29.         if (min.isEmpty()) {
  30.             min.add(new Node(0, x));
  31.         } else {
  32.             Node last = min.get(min.size() - 1);
  33.             if (last.value < x) { //如果入栈的数比min末尾的数据大，则在min末尾前插入新入栈的数据
  34.                 min.set(min.size() - 1, new Node(min.size(), x));
  35.                 min.add(last);
  36.             } else //如果入栈的数为最小值，直接插入min数组中
  37.                 min.add(new Node(min.size(), x));
  38.         }
  39.     }
  41.     public void pop() {
  42.         // 在min数组中，出栈的数据要么在末尾，要么在末尾-1的位置
  43.         if (min.get(min.size() - 1).index == data.size() - 1) { //出栈的数据在min末尾
  44.             min.remove(min.size() - 1);
  45.         } else {
  46.             Node last = min.get(min.size() - 1);
  47.             min.set(min.size() - 2, last);
  48.             min.remove(min.size() - 1);
  49.         }
  50.         data.remove(data.size() - 1);
  51.     }
  53.     public int top() {
  54.         return data.get(data.size() - 1);
  55.     }
  57.     public int getMin() {
  58.         return min.get(min.size() - 1).value;
  59.     }
  61.     class Node {
  62.         public int index, value;
  64.         public Node(int index, int value) {
  65.             this.index = index;
  66.             this.value = value;
  67.         }
  68.     }
  69. }
  71. /**
  72.  * Your MinStack object will be instantiated and called as such:
  73.  * MinStack obj = new MinStack();
  74.  * obj.push(x);
  75.  * obj.pop();
  76.  * int param_3 = obj.top();
  77.  * int param_4 = obj.getMin();
  78.  */