前言

在单调栈基础题中，经常需要类似这种的解题思路：在 $O(n)$ 的时间复杂度内求出数组中各个元素右侧第一个更大的元素及其下标，然后一并得到其他信息。

在进阶题中，主要考察借助单调栈的模拟。

本篇主要围绕基础部分讲解，读者掌握后基本能应对非高级岗位面试中的单调栈部分（如果出现的话）。

原理

1 / 10

这样 arr[0] 右侧第一个更大的元素为 arr[4]。根据 0 4 arr[0] arr[4] 能组成很多信息。
对于 arr[1], arr[2] ... 以此类推。
arr[4], arr[5] 右侧不存在更大的元素。

代码

class Solution {
public:
    vector<int> monotonicStack(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        stack<int> st;
      
      	for (int i = 0; i < n; ++i) {
            while (!st.empty() && nums[i] > nums[st.top()]) {
                int prevI = st.top();
                ans[prevI] = i;
                st.pop();
	            // 还可以针对 prevI, i, nums[prevI], nums[i] 做些其他的处理 
            }
            st.push(i);
        }
        
      return ans;
    }
};

总结与扩展

扩展并归纳一下，在 while 的执行条件中，将数组元素与栈顶元素比较时：

• 右侧第一个 更大（可相等） 元素对应 >=
• 右侧第一个 更大（不可相等） 元素对应 >
• 右侧第一个 更小元素（可相等） 元素对应 <=
• 右侧第一个 更小元素（不可相等） 元素对应 <

还可以镜像处理，逆向遍历数组并维护单调栈，得到各元素左侧相应的信息。

练习

可能涉及一些变形，但核心原理不变。

1. 每日温度
2. 下一个更大元素 I
3. 下一个更大元素 II
4. 柱状图中最大的矩形
5. 接雨水及个人题解（这道题在面试中出现原题的几率较高，建议掌握最优的双指针解法即可）

有进阶需求可参考灵茶山艾府给的单调栈题单。

推广

笔者著有 Leetbooks 《图论入门》，《图论进阶》，且在陆续写其他教程。致力于提升广大读者真正的算法水平，并兼顾不同阶段的读者，如海内外本科阶段、硕士阶段、职场面试、算法竞赛。

欢迎读者给出反馈或者建议！