单调栈

单调栈是一种运用栈数据结构来解决一些特定问题的解题技巧。它主要用于解决需要快速寻找一个元素左(或右)边第一个比它大(或小)的元素的问题。

使用单调栈的基本思路是保持栈内的元素单调递增或单调递减，栈顶元素是当前栈内最大或最小的元素，同时记录下每个元素的相关信息，如坐标、面积、数量等，根据这些信息计算出所需的结果。

单调栈的实现主要有两种，第一种是从前往后遍历数组，第二种是从后往前遍历数组。

寻找数组右侧第一个比它大的数

第一种实现方式：

// 从前往后遍历
vector<int> nextGreaterElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> res(n, -1); // 右侧没有比它大的数时对应res为-1，所以初始值全部设置为-1

    for(int i = 0; i < n; ++i)
    {
        // 当前元素大于栈顶元素时，当前元素就是栈顶元素右侧第一个大于栈顶的元素，并将栈顶出栈
        while(!s.empty() && nums[i] > nums[s.top()])    
        {
            res[s.top()] = i;
            s.pop();
        }
        s.emplace(i);
    }
    return res;
}

第二种实现方式：

// 从后往前遍历
vector<int> nextGreaterElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> res(n, -1); // 右侧没有比它大的数时对应res为-1，所以初始值全部设置为-1

    for(int i = n - 1; i >= 0; --i)     
    {
        // 栈顶元素在当前元素右侧，当栈顶元素小于或等于当前元素的时候，将其出栈，继续寻找当前元素右侧第一个比它大的元素
        while(!s.empty() && nums[s.top()] <= nums[i])  
            s.pop();
        res[i] = s.empty() ? -1 : s.top();
        s.emplace(i);
    }
}

寻找数组右侧第一个比它小的数

第一种实现方式：

// 从前往后遍历
vector<int> nextSmallerElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> right(n, -1); // 右侧没有比它小的数时对应res为-1，所以初始值全部设置为-1

    for(int i = 0; i < n; ++i)     
    {
        
        while(!s.empty() && nums[i] <= nums[s.top()])  
        {
            right[s.top()] = i;
            s.pop();
        }
        s.emplace(i);
    }
}

第二种实现方式：

// 从后往前遍历
vector<int> nextSmallerElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> right(n, -1); // 右侧没有比它小的数时对应res为-1，所以初始值全部设置为-1
    
    for(int i = n - 1; i >= 0; --i)
    {
        while(!s.empty() && nums[i] <= nums[s.top()])
            s.pop();
        right[i] = s.empty() ? -1 : s.top();
        s.emplace(i);
    }
    return right;
}

寻找数组右侧第一个满足某个条件的数

观察上面两个算法的实现，可以发现，以从前往后遍历为例，他们的框架其实是一样的:

// 从前往后遍历
vector<int> nextSatisfiedElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> res(n, -1);

    for(int i = 0; i < n; ++i)
    {
        while(!s.empty() && `nums[i]满足nums[s.top()]的条件`)    
        {
            res[s.top()] = i;
            s.pop();
        }
        s.emplace(i);
    }
    return res;
}

从后往前遍历：

// 从后往前遍历
vector<int> nextSatisfiedElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> right(n, -1); 
    
    for(int i = n - 1; i >= 0; --i)
    {
        while(!s.empty() && `nums[s.top()]不满足nums[i]的条件`)
            s.pop();
        right[i] = s.empty() ? -1 : s.top();
        s.emplace(i);
    }
    return right;
}

寻找数组左侧第一个满足某个条件的数

从前往后遍历：

// 从前往后遍历
vector<int> nextSatisfiedElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> left(n, -1); 
    
    for(int i = n - 1; i >= 0; --i)
    {
        while(!s.empty() && `nums[s.top()]不满足nums[i]的条件`)
            s.pop();
        left[i] = s.empty() ? -1 : s.top();
        s.emplace(i);
    }
    return right;
}

从后往前遍历:

// 从后往前遍历
vector<int> nextSatisfiedElement(vector<int> &nums)
{
    int n = nums.size();
    stack<int> s;
    vector<int> left(n, -1); 
    
    for(int i = n - 1; i >= 0; --i)
    {
        while(!s.empty() && `nums[i]满足nums[s.top()]的条件`)
        {
            left[s.top()] = i;
            s.pop();
        }
        s.emplace(i);
    }
    return right;
}

attention

寻找左边第一个满足某个条件的数和寻找右边第一个满足条件的数，从前往后遍历和从后往前遍历的循环条件刚好是相反的