🧠 单调栈

✅ 什么时候用

👉 题目出现这三个词 → 直接上单调栈：

  • 右边 / 左边
  • 第一个
  • 更大 / 更小

⚡ 核心：谁被弹出，谁结算答案

⭐ 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 1. 初始化
int n = nums.length;
int[] res = new int[n];
// 默认值按题目决定：-1（不存在） / 0（距离）
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>();

// 2. 遍历数组
for (int i = 0; i < n; i++) {
    // 👉 找更大：>    找更小：<
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        int idx = stack.pop();   // 谁被弹出，谁结算
        res[idx] = i - idx;      // 或 nums[i]，看题目要什么
    }
    stack.push(i); // 存下标，不是值
}

// 3. 返回结果
return res;
// ⚠️ 栈里剩下的元素 → 没找到答案，保持默认值 -1

🎬 模板运行动画（以每日温度 [73,74,75,71,69,72,76,73] 为例）

// 1. 初始化 int n = nums.length; int[] res = new int[n]; Arrays.fill(res, 0); Deque<Integer> stack = new ArrayDeque<>(); // 2. 遍历数组 for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { int idx = stack.pop(); res[idx] = i - idx; } stack.push(i); } // 3. 返回 res // ⚠️ 栈里剩下的 → 保持默认值 0
👋 点击 下一步 开始，看模板每一行怎么执行
输入数组 nums
栈（存下标，栈顶在右）
空栈
结果数组 res
当前 i 在栈中 被弹出 已结算

🔑 核心要点

栈里存什么？

下标 index，不是值。目的不是排序，而是”填答案数组”。

答案容器怎么选？

👉 答案跟下标走 → 数组
👉 答案跟值走 → 哈希表

While 条件怎么判断？

👉 找更大 → while nums[i] > nums[top]
👉 找更小 → while nums[i] < nums[top]

方向怎么定？

👉 找右边 → 从左往右遍历
👉 找左边 → 从右往左遍历

栈里剩余元素？

⚠️ 遍历结束后栈里还有元素 → 没找到答案，保持默认值

📝 练习题

1. LeetCode 739. 每日温度

题意： 给定每天温度数组，求每天要等几天才能遇到更高温度，没有则为 0。

🏷️ 这题 = 单调栈「找右边第一个更大元素」
👉 关键：res[idx] = i - idx（温度差 = 当前下标 - 栈顶下标）

2. LeetCode 496. 下一个更大元素 I

题意： nums1 是 nums2 的子集，对 nums1 每个元素找它在 nums2 中右侧第一个更大的值，没有返回 -1。

🏷️ 这题 = 单调栈 + 哈希表映射
👉 关键：先对 nums2 建「值 → 下一个更大值」的 map，再用 nums1 查表

3. LeetCode 503. 下一个更大元素 II

题意： 循环数组，找每个元素的下一个更大元素，不存在返回 -1。

🏷️ 这题 = 单调栈 + 循环数组
👉 关键：遍历 2*n，下标用 i % n（循环 = 遍历两遍 + 取模）