“下一个更大元素”问题是为数组每个位置i找其右侧第一个严格大于nums[i]的元素值，找不到则为-1；需用单调递减栈存未解下标、一次遍历实现O(n)时间复杂度。
什么是“下一个更大元素”问题
给定一个数组，对每个位置 i，要找它右边第一个严格大于 nums[i] 的元素值（不是下标），找不到就记为 -1。这不是简单遍历比较——暴力 O(n²) 在大数组上会超时，必须用单调栈优化。
用单调递减栈一次遍历搞定
核心思路：从左到右扫数组，但用栈存**还没找到答案的下标**；栈里对应元素值保持递减，一旦遇到更大的数，就不断弹栈并填写答案。
- 初始化空栈
stack和结果数组res（全填-1） - 遍历
i从0到n-1：
– 当栈非空且nums[i] > nums[stack.top()]，说明i就是栈顶下标对应的“下一个更大元素”位置
– 弹出栈顶idx，设res[idx] = nums[i]
– 重复直到不满足条件，再把i压栈 - 栈中剩余下标对应的结果保持
-1（右边没更大元素）
vector<int> nextGreaterElement(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && nums[i] > nums[st.top()]) {
res[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return res;
}
注意循环数组或重复元素的变体
原题若改成“循环数组”（末尾连回开头），只需把遍历长度翻倍，用 i % n 取模访问，其他逻辑不变；若数组含重复值，当前写法仍正确——因为比较用的是严格大于 >，相等时不触发弹栈，符合题意。
常见错误包括：res[st.top()] = i（错把下标当值）、while 条件漏判 !st.empty() 导致越界、用 >= 破坏“严格大于”要求。
立即学习“C++免费学习笔记（深入）”；
为什么不用 set 或 map 二分查找
有人想逆序遍历 + set 维护右侧已见元素，再用 upper_bound 找最小的大于当前值的数。这可行但常数大、代码长，且 set 插入和查询都是 O(log n)，总复杂度 O(n log n)，不如单调栈的 O(n) 稳定。实际刷题或工程中，只要题目明确“下一个更大”，单调栈就是最直接可靠的解法。
栈里存的是下标而非值，这点容易忽略——只有靠下标才能准确给 res 赋值；而比较时又必须用 nums[st.top()] 取值，二者缺一不可。
