包含min函数的栈

Posted on In Views: Waline: Symbols count in article: 200 Reading time ≈ 1 mins.

题解方法

  • 栈

栈

在每个元素入栈时把当前栈的最小值存储起来，在这之后无论何时，总能返回顶端元素对应的最小值。

  1. 使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
    1. 当一个元素要入栈时，取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中。
  2. 当一个元素要出栈时，辅助栈的栈顶元素也一并弹出。

核心代码

栈

1
2
3
4
5
6
7
8
9
10
public MinStack() {
    stack = new LinkedList<>();
    minStack = new LinkedList<>();
    minStack.push(Integer.MAX_VALUE);
}

public void push(int x) {
    stack.push(x);
    minStack.push(Math.min(x, minStack.peek()));
}

题目来源