day46 代码随想录算法训练营 单调栈专题1

1 今日打卡

每日温度 739. 每日温度 – 力扣（LeetCode）

下一个更大元素Ⅰ 496. 下一个更大元素 I – 力扣（LeetCode）

下一个更大元素Ⅱ 503. 下一个更大元素 II – 力扣（LeetCode）

2 每日温度

2.1 思路

核心数据结构：单调递增栈 栈中存储的是温度数组的索引，而非温度值（因为需要计算 “天数差”，索引差就是天数差）。 栈的特性：栈内索引对应的温度是单调递增的（这是 “单调栈” 的核心），保证了我们只需要遍历一次数组，时间复杂度为 O (n)。 2. 遍历逻辑（关键） 以 temperatures = [73,74,75] 为例： 初始化：st = [0]，res = [0,0,0] i=0：temperatures[0] (73) <= temperatures[0] (73) → 压入 0 → st = [0,0]（注：自比较不影响结果，后续会被覆盖） i=1：temperatures[1] (74) > temperatures[0] (73) → 进入 else： 栈顶是 0，res[0] = 1-0=1 → 弹出 0 → st = [0] 继续检查：temperatures[1] (74) > temperatures[0] (73) → res[0] = 1-0=1（重复赋值，结果不变）→ 弹出 0 → 栈空 压入 1 → st = [1] i=2：temperatures[2] (75) > temperatures[1] (74) → 进入 else： 栈顶是 1，res[1] = 2-1=1 → 弹出 1 → 栈空 压入 2 → st = [2] 最终结果：res = [1,1,0]（正确）

2.2 实现代码

import java.util.Deque;
import java.util.LinkedList;

class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// 1. 初始化双端队列作为单调栈，存储的是温度数组的索引（核心！不是温度值）
// LinkedList实现Deque，是Java推荐的栈实现方式（替代老旧的Stack类）
Deque<Integer> st = new LinkedList<>();

// 2. 先把第0天的索引压入栈，作为遍历的初始基准
st.push(0);

// 3. 获取温度数组长度，方便后续遍历
int len = temperatures.length;

// 4. 结果数组，默认初始化为0（符合题目“无更高温度则为0”的要求）
int[] res = new int[len];

// 5. 遍历每一天的温度（从第0天开始，和原版本从1开始逻辑一致，只是多了一次自比较）
for(int i = 0; i < len; i++) {
// 情况1：当前温度 <= 栈顶索引对应的温度
// 说明当前天还没找到更高温度，把当前天索引压入栈，继续等后面的天
if(temperatures[i] <= temperatures[st.peek()]) {
st.push(i);
}
// 情况2：当前温度 > 栈顶索引对应的温度（找到更高温度了）
else {
// 循环检查：只要栈不为空，且当前温度仍大于栈顶索引的温度
// 确保所有“比当前温度低”的栈内索引都能找到答案
while(!st.isEmpty() && temperatures[i] > temperatures[st.peek()]) {
// 计算栈顶索引对应的等待天数：当前天索引 – 栈顶索引
res[st.peek()] = i – st.peek();
// 栈顶索引已经找到答案，弹出栈（后续无需再处理）
st.pop();
}
// 处理完所有更小的温度后，把当前天索引压入栈，作为新的基准
st.push(i);
}
}
// 返回结果数组
return res;
}
}

3 下一个更大元素Ⅰ

3.1 思路

步骤 1：哈希表预处理（快速映射） 把 nums1 的「元素值 → 索引」存入 HashMap； 作用：遍历 nums2 时，能 O (1) 时间判断当前元素是否在 nums1 中，且直接拿到它在结果数组中的位置，避免嵌套循环。 步骤 2：单调栈处理 nums2（找下一个更大元素） 单调栈的核心是维护一个 “递增” 的索引栈，遍历 nums2 时： 若当前元素 ≤ 栈顶元素：说明当前元素不是栈顶元素的 “下一个更大元素”，压入栈等待后续处理； 若当前元素 > 栈顶元素：说明当前元素是栈顶元素的 “下一个更大元素”，循环弹出栈顶元素（直到栈空或当前元素不更大），并通过哈希表更新 nums1 的结果。 步骤 3：结果填充 结果数组初始化为 – 1（题目要求无更大元素时返回 – 1）； 只有在 nums2 中找到 nums1 元素的 “下一个更大元素” 时，才更新对应位置的值，未更新的位置保持 – 1。 用例子验证逻辑（更直观） 以 nums1 = [4,1,2]，nums2 = [1,3,4,2] 为例： 初始化：res = [-1,-1,-1]，map = {4:0, 1:1, 2:2}，st = [0]（nums2[0]=1）； i=1（nums2 [1]=3）：3>1 → 进入 else： 栈顶 0 对应 nums2 [0]=1，在 map 中 → res[1] = 3； 弹出 0 → 栈空 → 压入 1 → st = [1]； i=2（nums2 [2]=4）：4>3 → 进入 else： 栈顶 1 对应 nums2 [1]=3，不在 map 中 → 直接弹出 1 → 栈空； 压入 2 → st = [2]； i=3（nums2 [3]=2）：2<4 → 压入 3 → st = [2,3]； 最终结果：res = [-1,3,-1]（符合预期）。 总结 核心思想：用哈希表快速映射 nums1 的元素位置，用单调栈 O (n) 时间找到 nums2 中每个元素的下一个更大元素，整体时间复杂度 O (n1 + n2)（n1 是 nums1 长度，n2 是 nums2 长度）。 关键细节：栈中存储的是 nums2 的索引（而非值），且找到更大元素后必须无条件弹出栈顶，保证单调栈的特性。 初始化技巧：结果数组先填充 – 1，避免后续处理 “无更大元素” 的边界情况。

3.2 实现代码

class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 1. 获取nums1的长度，用于初始化结果数组
int len1 = nums1.length;
// 2. 初始化结果数组，题目要求“无更大元素则返回-1”，所以先用Arrays.fill填充-1
int[] res = new int[len1];
Arrays.fill(res, -1);

// 3. 哈希表：存储nums1的“元素-索引”映射
// 作用：后续遍历nums2时，能快速判断当前元素是否在nums1中，且找到其在res中的位置
HashMap<Integer, Integer> map = new HashMap<>();
int len2 = nums2.length;
for(int i = 0; i < len1; i++) {
map.put(nums1[i], i); // key：nums1的元素，value：该元素在nums1中的索引
}

// 4. 单调递增栈：存储nums2的索引（核心！不是元素值）
// 栈特性：栈内索引对应的nums2元素是单调递增的，用于高效找“下一个更大元素”
Deque<Integer> st = new LinkedList<>();
st.push(0); // 先压入nums2第一个元素的索引，作为遍历基准

// 5. 遍历nums2的剩余元素（从第1个开始）
for(int i = 1; i < len2; i++) {
// 情况1：当前元素 <= 栈顶索引对应的元素 → 未找到更大元素
// 把当前索引压入栈，继续等待后面的更大元素
if(nums2[i] <= nums2[st.peek()]) {
st.push(i);
}
// 情况2：当前元素 > 栈顶索引对应的元素 → 找到“下一个更大元素”
else {
// 循环检查：只要栈不为空，且当前元素仍大于栈顶元素
// 确保栈中所有比当前元素小的元素都能找到“下一个更大元素”
while(!st.isEmpty() && nums2[i] > nums2[st.peek()]) {
// 检查栈顶元素是否在nums1中（通过哈希表快速判断）
if(map.containsKey(nums2[st.peek()])) {
// 找到该元素在nums1中的索引
int index = map.get(nums2[st.peek()]);
// 更新结果数组：该位置的“下一个更大元素”就是当前nums2[i]
res[index] = nums2[i];
}
// 关键：无论栈顶元素是否在nums1中，都要弹出！
// 因为栈顶元素已经找到“下一个更大元素”，完成使命
st.pop();
}
// 处理完所有更小的元素后，将当前索引压入栈，作为新的基准
st.push(i);
}
}
// 6. 返回结果数组
return res;
}
}

4 下一个更大元素Ⅱ

4.1 思路

1. 如何模拟 “循环数组”？

循环数组的本质是 “遍历完数组后，再从头遍历一次”，但不需要真的拼接数组，而是通过取模运算 i % nums.size() 实现： 遍历范围从 0 ~ 2*n-1（n 是数组长度），相当于把数组 “复制一份接在后面”； 用 i % n 映射到原数组的索引，既模拟了循环，又避免了额外空间。

2. 单调栈的作用（和前两题一致） 栈中存储原数组的索引，且索引对应的元素保持单调递增； 遍历过程中，找到当前元素是哪些栈内元素的 “下一个更大元素”，并更新结果数组。

3. 整体逻辑 初始化结果数组为 – 1（默认无更大元素）； 用单调栈存储未找到更大元素的索引； 遍历 0 ~ 2*n-1（模拟两次遍历数组），通过取模映射到原数组索引； 对比当前元素和栈顶元素： 更小 / 相等：压栈（继续等更大元素）； 更大：弹栈并更新结果（找到目标元素）。

4.2 实现代码

class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
// 1. 初始化结果数组，所有元素默认-1（无更大元素时返回-1）
vector<int> result(nums.size(), -1);
// 2. 边界处理：空数组直接返回
if (nums.size() == 0) return result;

// 3. 单调递增栈：存储nums的索引（核心，不是元素值）
stack<int> st;
st.push(0); // 先压入第一个元素的索引作为基准

// 4. 遍历范围是0 ~ 2n-1（模拟遍历两次数组，实现循环效果）
for (int i = 1; i < nums.size() * 2; i++) {
// 关键：用i % nums.size()映射到原数组的索引，模拟循环
int curIndex = i % nums.size();
int topIndex = st.top();

// 情况1：当前元素 < 栈顶元素 → 未找到更大元素，压入当前索引
if (nums[curIndex] < nums[topIndex]) {
st.push(curIndex);
}
// 情况2：当前元素 == 栈顶元素 → 相等不算更大，压入当前索引
else if (nums[curIndex] == nums[topIndex]) {
st.push(curIndex);
}
// 情况3：当前元素 > 栈顶元素 → 找到“下一个更大元素”
else {
// 循环弹出栈顶，直到栈空或当前元素不大于栈顶元素
while (!st.empty() && nums[curIndex] > nums[st.top()]) {
// 更新结果数组：栈顶索引的下一个更大元素是当前元素
result[st.top()] = nums[curIndex];
st.pop(); // 栈顶元素已找到答案，弹出
}
// 压入当前索引，继续处理后续元素
st.push(curIndex);
}
}
return result;
}
};