数据结构与算法-单调栈
目录
单调栈总述
[!blue]
适用场景：凡是问「某个元素左边 / 右边第一个比它大（小）的元素在哪」，或者要为每个元素确定「以它为最值的辐射范围」，都应该第一时间想到单调栈。暴力解法对每个元素向一侧扫描是 $O(n^2)$，单调栈把它压到 $O(n)$。
方向选择（单调性一律指从栈底到栈顶的方向）：
- 单调递增栈：栈顶被更小的元素弹出，所以适合找左 / 右边第一个比当前值小的元素。
- 单调递减栈：栈顶被更大的元素弹出，所以适合找左 / 右边第一个比当前值大的元素。
记忆方式：当前元素把「破坏单调性」的栈顶弹出，被弹出的元素在出栈那一刻就找到了答案——答案要么是「弹它出栈的当前元素」（一侧），要么还要配合「弹出后暴露的新栈顶」（另一侧）。
写单调栈只需回答三个问题：栈里存什么（存下标还是存值——凡是答案与位置、距离有关就必须存下标）；什么时候弹（当前元素与栈顶比较的方向，以及相等时弹不弹）；弹出时结算什么（被弹出元素的答案由「当前元素」和「新栈顶」共同确定）。
$O(n)$ 均摊分析：虽然循环里套着 while，但每个元素至多入栈一次、出栈一次，所有弹栈操作的总次数不超过 $n$，因此整体时间是 $O(n)$ 而不是 $O(n^2)$。这是单调栈复杂度分析的标准说法。
单调递减栈
496. 下一个更大元素 I
核心观察：单调栈模板题。
nums1是nums2的子集，只要为nums2中每个元素求出「下一个更大元素」，nums1的查询就是查表。栈里存什么：还没找到答案的元素值（从栈底到栈顶递减）。因为
nums2无重复元素，可以直接存值而不必存下标。什么时候弹：当前值严格大于栈顶时。弹出时结算什么：被弹出元素的「下一个更大元素」就是当前值，写入哈希表。遍历结束后仍留在栈里的元素没有答案，查表时返回 -1。
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> nextGreater = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int num : nums2) {
// 当前值弹出所有比它小的栈顶，栈顶的答案就是当前值
while (!stack.isEmpty() && num > stack.peek()) {
nextGreater.put(stack.pop(), num);
}
stack.push(num);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = nextGreater.getOrDefault(nums1[i], -1);
}
return res;
}
}
func nextGreaterElement(nums1 []int, nums2 []int) []int {
nextGreater := make(map[int]int)
var stack []int
for _, num := range nums2 {
// 当前值弹出所有比它小的栈顶，栈顶的答案就是当前值
for len(stack) > 0 && num > stack[len(stack)-1] {
nextGreater[stack[len(stack)-1]] = num
stack = stack[:len(stack)-1]
}
stack = append(stack, num)
}
res := make([]int, len(nums1))
for i, num := range nums1 {
if v, ok := nextGreater[num]; ok {
res[i] = v
} else {
res[i] = -1
}
}
return res
}
- 时间复杂度：$O(m + n)$，
nums2每个元素至多进出栈一次，nums1的查询是 $O(1)$ 查表。- 空间复杂度：$O(n)$，栈和哈希表最多存
nums2的全部元素。
503. 下一个更大元素 II
核心观察：循环数组的标准处理——下标遍历 $2n$ 次、用
i % n取值，相当于把数组拼接了一遍，让每个元素都能「看到」自己左边的部分。栈里存什么：下标（数组有重复值，且第二轮要按位置结算，必须存下标），对应值从栈底到栈顶递减；只在第一轮（
i < n）入栈，第二轮只负责弹栈结算。什么时候弹：当前值严格大于栈顶对应值时。弹出时结算什么：栈顶下标的答案就是当前值。答案初始化为 -1，转完两圈还留在栈里的位置就是没有更大元素的位置。
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && num > nums[stack.peek()]) {
res[stack.pop()] = num;
}
// 只在第一轮入栈，第二轮只结算
if (i < n) {
stack.push(i);
}
}
return res;
}
}
func nextGreaterElements(nums []int) []int {
n := len(nums)
res := make([]int, n)
for i := range res {
res[i] = -1
}
var stack []int
for i := 0; i < 2*n; i++ {
num := nums[i%n]
for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
res[stack[len(stack)-1]] = num
stack = stack[:len(stack)-1]
}
// 只在第一轮入栈，第二轮只结算
if i < n {
stack = append(stack, i)
}
}
return res
}
- 时间复杂度：$O(n)$，下标走 $2n$ 步，每个下标至多进出栈一次。
- 空间复杂度：$O(n)$，栈最多存 $n$ 个下标。
739. 每日温度
核心观察：问的是「等几天」而不是「等到多少度」，答案与距离有关，所以栈必须存下标。
栈里存什么：还没等到更高温度的日期下标，对应温度从栈底到栈顶递减。什么时候弹：当前温度严格高于栈顶对应温度时。弹出时结算什么：被弹出下标
pre的答案是i - pre，即两个下标之差。留在栈里的位置等不到更高温度，保持默认值 0。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int pre = stack.pop();
// 弹出时结算等待天数
res[pre] = i - pre;
}
stack.push(i);
}
return res;
}
}
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
res := make([]int, n)
var stack []int
for i := 0; i < n; i++ {
for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
pre := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 弹出时结算等待天数
res[pre] = i - pre
}
stack = append(stack, i)
}
return res
}
- 时间复杂度：$O(n)$，每个下标至多进出栈一次。
- 空间复杂度：$O(n)$，最坏情况（温度单调递减）栈存下全部下标。
901. 股票价格跨度
核心观察：跨度是「从今天往前数，连续小于等于今天价格的天数」，本质是往左找第一个严格更大的价格。被新价格吞并的旧价格以后不可能再成为任何一天的挡板——新价格更靠右且不低于它们——所以可以把它们的跨度合并进新价格后安全丢弃。
栈里存什么：二元组「价格、跨度」，价格从栈底到栈顶严格递减。什么时候弹：新价格大于等于栈顶价格时。弹出时结算什么：把被弹出元素的跨度累加到新价格的跨度上，最后新价格连同累计跨度入栈。
class StockSpanner {
// 栈存 [价格, 跨度]，价格从栈底到栈顶严格递减
private final Deque<int[]> stack = new ArrayDeque<>();
public StockSpanner() {
}
public int next(int price) {
int span = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
// 被吞并价格的跨度合并到当前价格上
span += stack.pop()[1];
}
stack.push(new int[]{price, span});
return span;
}
}
type StockSpanner struct {
stack [][2]int // [价格, 跨度]，价格从栈底到栈顶严格递减
}
func Constructor() StockSpanner {
return StockSpanner{}
}
func (s *StockSpanner) Next(price int) int {
span := 1
for len(s.stack) > 0 && s.stack[len(s.stack)-1][0] <= price {
// 被吞并价格的跨度合并到当前价格上
span += s.stack[len(s.stack)-1][1]
s.stack = s.stack[:len(s.stack)-1]
}
s.stack = append(s.stack, [2]int{price, span})
return span
}
- 时间复杂度：均摊 $O(1)$，$n$ 次调用总共 $O(n)$——每个价格至多入栈一次、出栈一次。
- 空间复杂度：$O(n)$，最坏情况（价格单调递减）栈存下全部价格。
316. 去除重复字母
核心观察：贪心 + 单调栈。要让结果字典序最小，靠前的字符应尽量小，栈中字符理想状态是递增的；但弹出栈顶有一个前提——栈顶字符在后面还会出现（
last[栈顶] > i），否则弹掉就再也凑不齐了。栈里存什么：当前构造出的答案字符序列，配一个
inStack标记去重——已经在栈里的字符直接跳过，它已经站在更优的位置上。什么时候弹：当前字符比栈顶小，且栈顶在后面还会出现时。弹出时结算什么：无需结算答案，只是把栈顶让位并清除它的在栈标记，遍历结束后栈中序列就是答案。
class Solution {
public String removeDuplicateLetters(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
StringBuilder stack = new StringBuilder();
boolean[] inStack = new boolean[26];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (inStack[c - 'a']) {
continue;
}
// 栈顶更大且后面还会出现时，才能放心弹出
while (stack.length() > 0 && c < stack.charAt(stack.length() - 1)
&& last[stack.charAt(stack.length() - 1) - 'a'] > i) {
inStack[stack.charAt(stack.length() - 1) - 'a'] = false;
stack.deleteCharAt(stack.length() - 1);
}
stack.append(c);
inStack[c - 'a'] = true;
}
return stack.toString();
}
}
func removeDuplicateLetters(s string) string {
var last [26]int
for i := 0; i < len(s); i++ {
last[s[i]-'a'] = i
}
var stack []byte
var inStack [26]bool
for i := 0; i < len(s); i++ {
c := s[i]
if inStack[c-'a'] {
continue
}
// 栈顶更大且后面还会出现时，才能放心弹出
for len(stack) > 0 && c < stack[len(stack)-1] && last[stack[len(stack)-1]-'a'] > i {
inStack[stack[len(stack)-1]-'a'] = false
stack = stack[:len(stack)-1]
}
stack = append(stack, c)
inStack[c-'a'] = true
}
return string(stack)
}
- 时间复杂度：$O(n)$，每个字符至多进出栈一次。
- 空间复杂度：$O(1)$，栈、
last、inStack都不超过 26 个小写字母的规模。
402. 移掉 K 位数字
核心观察：贪心——数字大小由高位主导，高位越小越好。只要某一位比它左边的相邻位小，删掉左边那位一定不亏。
栈里存什么：当前保留下来的数字序列，从栈底到栈顶单调不减。什么时候弹：当前数字严格小于栈顶，且还有删除额度（
k > 0）时。弹出时结算什么：消耗一次删除额度。遍历结束后k仍有剩余，说明序列整体不减，从末尾删掉最大的几位；最后去掉前导零，空串返回"0"。
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder stack = new StringBuilder();
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);
// 高位出现更小的数字时，删掉栈顶的大数字
while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
stack.append(c);
}
// 额度没用完，从末尾删掉最大的几位
stack.setLength(stack.length() - k);
int start = 0;
while (start < stack.length() && stack.charAt(start) == '0') {
start++;
}
String res = stack.substring(start);
return res.isEmpty() ? "0" : res;
}
}
func removeKdigits(num string, k int) string {
var stack []byte
for i := 0; i < len(num); i++ {
// 高位出现更小的数字时，删掉栈顶的大数字
for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, num[i])
}
// 额度没用完，从末尾删掉最大的几位
stack = stack[:len(stack)-k]
start := 0
for start < len(stack) && stack[start] == '0' {
start++
}
if start == len(stack) {
return "0"
}
return string(stack[start:])
}
- 时间复杂度：$O(n)$，每个数字至多进出栈一次，去前导零是一次线性扫描。
- 空间复杂度：$O(n)$，栈最多存全部数字。
581. 最短无序连续子数组
核心观察：一个位置需要参与重排，当且仅当它右边存在比它小的元素，或它左边存在比它大的元素。两个方向各用一次单调栈，分别找出「需要重排的最左下标」和「需要重排的最右下标」。
栈里存什么：下标。从左往右维护单调递增栈，什么时候弹：当前值比栈顶对应值小时；弹出时结算什么：被弹出的下标右侧存在更小值，必须重排，用它更新左边界的最小值。再从右往左对称地维护单调递减栈，被弹出的下标左侧存在更大值，用它更新右边界的最大值。若右边界不大于左边界说明数组已有序，返回 0。追问优化：改成两次线性扫描分别维护前缀最大值与后缀最小值，空间可降到 $O(1)$。
class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int left = n, right = -1;
Deque<Integer> stack = new ArrayDeque<>();
// 从左往右：被弹出的下标右侧存在更小值，必须重排
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
left = Math.min(left, stack.pop());
}
stack.push(i);
}
stack.clear();
// 从右往左：被弹出的下标左侧存在更大值，必须重排
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
right = Math.max(right, stack.pop());
}
stack.push(i);
}
return right > left ? right - left + 1 : 0;
}
}
func findUnsortedSubarray(nums []int) int {
n := len(nums)
left, right := n, -1
var stack []int
// 从左往右：被弹出的下标右侧存在更小值，必须重排
for i := 0; i < n; i++ {
for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if top < left {
left = top
}
}
stack = append(stack, i)
}
stack = stack[:0]
// 从右往左：被弹出的下标左侧存在更大值，必须重排
for i := n - 1; i >= 0; i-- {
for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if top > right {
right = top
}
}
stack = append(stack, i)
}
if right <= left {
return 0
}
return right - left + 1
}
- 时间复杂度：$O(n)$，两趟遍历，每趟每个下标至多进出栈一次。
- 空间复杂度：$O(n)$，栈最多存全部下标；改用前缀最大值 / 后缀最小值的写法可降到 $O(1)$。
456. 132 模式
核心观察：132 模式即下标
i < j < k且nums[i] < nums[k] < nums[j]。固定「2」来判定最容易：只要找到一个尽量大的「2」，再往左遇到任何比它小的数就是「1」。于是从右往左遍历，让栈维护候选的「3」。栈里存什么：当前元素右侧、还没被确认为「2」的候选「3」，从栈底到栈顶递减。什么时候弹：当前元素严格大于栈顶时——当前元素成为更靠左的「3」，被弹出的栈顶右侧存在比它大的数，恰好是合法的「2」。弹出时结算什么：用被弹出的值更新
second（已确认的最大的「2」）。每轮先判断：当前元素比second还小，它就是「1」，直接返回true。
class Solution {
public boolean find132pattern(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>(); // 候选的 "3"，从栈底到栈顶递减
int second = Integer.MIN_VALUE; // 已确认的最大的 "2"
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] < second) {
return true; // nums[i] 就是 "1"
}
while (!stack.isEmpty() && nums[i] > stack.peek()) {
second = stack.pop();
}
stack.push(nums[i]);
}
return false;
}
}
func find132pattern(nums []int) bool {
var stack []int // 候选的 "3"，从栈底到栈顶递减
second := math.MinInt64 // 已确认的最大的 "2"
for i := len(nums) - 1; i >= 0; i-- {
if nums[i] < second {
return true // nums[i] 就是 "1"
}
for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
second = stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
stack = append(stack, nums[i])
}
return false
}
- 时间复杂度：$O(n)$，从右往左一趟遍历，每个元素至多进出栈一次。
- 空间复杂度：$O(n)$，最坏情况（数组单调递增，从右往左看递减）栈存下全部元素。
单调递增栈
907. 子数组的最小值之和
核心观察：换个角度算贡献——不枚举子数组，而是求每个元素作为最小值能「管辖」多少个子数组。以
arr[top]为最小值的子数组，左端点可选top - left个（left是左侧第一个更小元素的下标），右端点可选i - top个（i是右侧第一个小于等于元素的下标），贡献即三者相乘。一边取严格小于、一边取小于等于，是为了避免相等元素重复计数。栈里存什么：下标，对应值从栈底到栈顶递增。什么时候弹：
i == n作为哨兵强制清空，或当前值小于等于栈顶对应值时。弹出时结算什么：被弹出下标top的辐射范围由「新栈顶left」和「当前下标i」确定，累加贡献arr[top] * (top - left) * (i - top)并取模。
class Solution {
public int sumSubarrayMins(int[] arr) {
final int MOD = 1_000_000_007;
int n = arr.length;
long res = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
// i == n 作为哨兵，把栈清空
while (!stack.isEmpty() && (i == n || arr[stack.peek()] >= arr[i])) {
int top = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
res = (res + (long) arr[top] * (top - left) * (i - top)) % MOD;
}
if (i < n) {
stack.push(i);
}
}
return (int) res;
}
}
func sumSubarrayMins(arr []int) int {
const mod = 1_000_000_007
n := len(arr)
res := 0
var stack []int // 单调递增栈，存下标
for i := 0; i <= n; i++ {
// i == n 作为哨兵，把栈清空
for len(stack) > 0 && (i == n || arr[stack[len(stack)-1]] >= arr[i]) {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
left := -1
if len(stack) > 0 {
left = stack[len(stack)-1]
}
res = (res + arr[top]*(top-left)*(i-top)) % mod
}
if i < n {
stack = append(stack, i)
}
}
return res
}
- 时间复杂度：$O(n)$，每个下标至多进出栈一次，哨兵只增加一轮循环。
- 空间复杂度：$O(n)$，最坏情况（数组单调递增）栈存下全部下标。
42. 接雨水
核心观察（单调栈，按行接水）：水横向一层一层地接。当出现比栈顶更高的柱子时，栈顶就成了凹槽的底：左边的新栈顶是左挡板，当前柱子是右挡板，中间这一层水可以立即结算。
栈里存什么：下标，对应高度从栈底到栈顶递减。什么时候弹：当前高度严格大于栈顶高度时。弹出时结算什么：弹出的下标是凹槽底部
bottom；若弹出后栈空说明左边没有挡板、接不住水，直接跳出；否则这一层水量 = 宽度i - left - 1× 高度差min(height[i], height[left]) - height[bottom]，按层累加。
class Solution {
public int trap(int[] height) {
int res = 0;
Deque<Integer> stack = new ArrayDeque<>(); // 存下标，高度从栈底到栈顶递减
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottom = stack.pop(); // 凹槽底部
if (stack.isEmpty()) {
break; // 左边没有挡板，接不住水
}
int left = stack.peek();
int width = i - left - 1;
int depth = Math.min(height[i], height[left]) - height[bottom];
res += width * depth;
}
stack.push(i);
}
return res;
}
}
func trap(height []int) int {
res := 0
var stack []int // 存下标，高度从栈底到栈顶递减
for i, h := range height {
for len(stack) > 0 && h > height[stack[len(stack)-1]] {
bottom := stack[len(stack)-1] // 凹槽底部
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break // 左边没有挡板，接不住水
}
left := stack[len(stack)-1]
width := i - left - 1
depth := min(h, height[left]) - height[bottom]
res += width * depth
}
stack = append(stack, i)
}
return res
}
- 时间复杂度：$O(n)$，每个下标至多进出栈一次，每次弹出结算一层水。
- 空间复杂度：$O(n)$，最坏情况（高度单调递减）栈存下全部下标。
双指针解法（按列接水，面试更常写）：每个位置能接的水 =
min(左侧最大高度, 右侧最大高度) - 自身高度。左右指针相向移动，谁矮移谁：当height[left] < height[right]时，left位置的瓶颈一定是leftMax——右边至少有一根更高的柱子兜底，无需知道右侧真正的最大值；反之亦然。
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int res = 0;
while (left < right) {
// 矮的一侧瓶颈已确定，可以立即结算并移动
if (height[left] < height[right]) {
if (height[left] < leftMax) {
res += leftMax - height[left];
} else {
leftMax = height[left];
}
left++;
} else {
if (height[right] < rightMax) {
res += rightMax - height[right];
} else {
rightMax = height[right];
}
right--;
}
}
return res;
}
}
func trap(height []int) int {
left, right := 0, len(height)-1
leftMax, rightMax := 0, 0
res := 0
for left < right {
// 矮的一侧瓶颈已确定，可以立即结算并移动
if height[left] < height[right] {
if height[left] < leftMax {
res += leftMax - height[left]
} else {
leftMax = height[left]
}
left++
} else {
if height[right] < rightMax {
res += rightMax - height[right]
} else {
rightMax = height[right]
}
right--
}
}
return res
}
- 时间复杂度：$O(n)$，左右指针合计移动 $n$ 步。
- 空间复杂度：$O(1)$，只用常数个变量，优于单调栈解法。