本文总结单调栈算法。

原问题

学习一个算法，我们需要清楚的是：这个算法最原始的问题背景是什么样的？

下一个更小元素

给定一个数组 nums，返回每个元素的下一个更小的元素的下标 res，即 res[i] 记录的是 nums[i] 右端第一个比它小的元素的下标（不存在则为 -1 ）。

例如 nums = [2,1,2,4,3]，那么 res = [1, -1, -1, 4, -1] .

从左往右扫描数组，栈底到栈顶维持升序（不要求严格），当扫描当前元素 nums[i] = x 时，如果需要出栈（说明栈顶严格大于当前的 x ），那么 x 就是出栈元素的下一个更小元素。

vector<int> nextSmallerNumber(vector<int> &nums)
{
    int n = nums.size(), idx = -1;
    vector<int> res(n, -1);
    stack<int> stk;
    for (int i = 0; i < n; i++)
    {
        while (!stk.empty() && nums[stk.top()] > nums[i])
        {
            idx = stk.top(), stk.pop();
            res[idx] = i;
        }
        stk.emplace(i);
    }
    return res;
}

相关题目：

• 两侧的更小值

下一个更大元素

给定一个数组 nums，返回每个元素的下一个更大的元素的下标 res，即 res[i] 记录的是 nums[i] 右端第一个比它大的元素的下标（不存在则为 -1 ）。

例如 nums = [2,1,2,4,3]，那么 res = [3, 2, 3, -1, -1] .

从左往右扫描数组，栈底到栈顶维持降序（不要求严格），当扫描当前元素 nums[i] = x 时，如果需要出栈（说明栈顶严格小于当前的 x ），那么 x 就是出栈元素的下一个更大元素。

vector<int> nextGreaterNumber(vector<int> &&nums)
{
    int n = nums.size(), idx;
    vector<int> res(n, -1);
    stack<int> stk;
    for (int i = 0; i < n; i++)
    {
        while (!stk.empty() && nums[stk.top()] < nums[i])
        {
            idx = stk.top(), stk.pop();
            res[idx] = i;
        }
        stk.emplace(i);
    }
    return res;
}

类似题目：

• 496. 下一个更大元素 I
• 503. 下一个更大元素 II
• 739. 每日温度

Leetcode

下一个更大元素 I

题目：496. 下一个更大元素 I

题目保证 nums1 是 nums2 的子集，首先在 nums2 先做一次「下一个更大」元素，使用一个哈希表记录结果。

然后扫描 nums1 ，把哈希表的结果按序填入数组 res 即可。

每次自己写出了最优解，并且官方也是同一思路，都会觉得好有成就感