剑指 Offer 30. 包含min函数的栈
单调栈
题目链接-来源:力扣(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 | class MinStack { |
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.