题目链接

题目描述

设计一个支持 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 操作总是在 非空栈 上调用。
解题思路
方法一：辅助栈
通过一个人辅助栈保存每一次的最小值，并随着主栈操作。

时间复杂度 O(n) getMin()时间复杂的为O(1)
空间复杂度 O(2n)

方法一：优化辅助栈
变量minVal保存最小栈，主栈中保存当前值 - 最小值的差。
当前值小于最小值时，更新最小值，当前stack保存的值为负值（val - minVal < 0）。
pop时，当stack.top()小于0时，说明需要更新minVal，minVal更新为minVal = minVal - stack.peek()。
因为是差，可能存在越界情况，所以用Long保存。 ```java class MinStack { private Deque stack; private long minVal; public MinStack() {
```
  stack = new LinkedList<Long>();
  minVal = Long.MAX_VALUE;
```
}

public void push(int val) {
```
  if(val < minVal){
      stack.push(val - minVal);
      minVal = val;
  }else{
      stack.push(val - minVal);
  } 
```
}

public void pop() {
```
  if(stack.peek() < 0){
      minVal = minVal - stack.peek();
  }
  stack.poll();
```
}

public int top() {
```
  if(stack.peek() < 0){
      return (int)minVal;
  }
  return (int)(stack.peek() + minVal);
```
}

public int getMin() {
```
  return (int)minVal;
```
} }

/**

Your MinStack object will be instantiated and called as such:
MinStack obj = new MinStack();
obj.push(val);
obj.pop();
int param_3 = obj.top();
int param_4 = obj.getMin(); */ ```

时间复杂度 O(n) getMin()时间复杂的为O(1)
空间复杂度 O(n)

算法(leetcode 牛客网)

155. 最小栈

题目链接

题目描述

解题思路

方法一：辅助栈

方法一：优化辅助栈