单调栈

题目链接-来源:力扣(LeetCode)

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.

思路:

此题的难点在于如何用尽可能低的复杂度实现对当前「最小元素」的查找。
我们知道「最小堆」可以实现均摊复杂度为 O(logn) 的查找最小值的方式,距离我们要求的O(1)还有距离。
考虑我们每入栈一个元素,对当前栈中「最小值」的影响。假设我们压入了一个元素并且是「最小值」,我们记录这个最小值。当我们后续压入任何大于这个值的元素,都对「最小值」没有影响。只有当这个元素出栈了,或者我们又压入了更小的「新最小值」,才需要更新最小值。而由于栈的「后进先出」特性,这个「新最小值」是会比原来的「最小值」更早取出的,这个特性恰好也符合栈的「后进先出」特性,于是我们可以用另一个栈来存储这一系列最小值。这个栈中的元素自底向顶单调非增,于是称作「单调栈」。
「单调栈」的栈顶元素就是当前的最小值,当压入了相等或更小的值时,我们也将其压入单调栈当中。当出栈的元素与栈顶元素相等时,意味着这个「最小值」我们需要丢弃,于是单调栈也随之出栈。
时间复杂度:O(1)
空间复杂度:O(n)

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MinStack {

/** initialize your data structure here. */
private Stack<Integer> a;
private Stack<Integer> b;

public MinStack() {
a = new Stack<>();
b = new Stack<>();
}

public void push(int x) {
a.push(x);
if (b.isEmpty() || x <= b.peek()) {
b.push(x);
}
}

public void pop() {
int v = a.pop();
if (b.peek().equals(v)) {
b.pop();
}
}

public int top() {
return a.peek();
}

public int min() {
return b.peek();
}
}