m8rZMVYbtdFlJH7

单调栈

引用链接：

单调栈是一种数据结构，通常用于解决某些与数组或序列中的顺序相关的问题。它主要用于保持一个栈中的元素以单调递增或单调递减的顺序，因此被称为“单调栈”。单调栈特别适合解决需要在一个数组中寻找与每个元素有关的下一个更大（或更小）元素的问题，典型例子包括 “下一个更大元素”、”下一个更小元素” 等。

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

为了描述方便，以下举例及伪代码以维护一个整数的单调递增栈为例。

过程

插入

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例如，栈中自顶向下的元素为 $\{0,11,45,81\}$ 。

插入元素时为了保证单调性需要依次弹出元素，操作后栈变为 $\{14,45,81\}$ 。

用伪代码描述如下：
1
2
3
4
insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)
使用

自然就是从栈顶读出来一个元素，该元素满足单调性的某一端。

例如举例中取出的即栈中的最小值。
单调栈可以在时间复杂度为 O(n)的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。

所以单调栈一般用于解决一下几种问题：

寻找左侧第一个比当前元素大的元素。

寻找左侧第一个比当前元素小的元素。

寻找右侧第一个比当前元素大的元素。

寻找右侧第一个比当前元素小的元素。

基础介绍

单调栈的特点

单调栈具有以下特点：

单调递增栈：栈中元素保持递增（栈底到栈顶）；通常用于找下一个更小元素。
单调递减栈：栈中元素保持递减（栈底到栈顶）；通常用于找下一个更大元素。
时间复杂度：单调栈的典型时间复杂度是 O(n)，因为每个元素只会入栈和出栈一次。

通过使用单调栈，可以在 O(n) 的时间复杂度内解决一些序列中的查找问题，例如查找下一个比当前元素大的元素。

单调栈的应用场景

下一个更大元素：给定一个数组，对每个元素找到右边第一个比它大的元素。
直方图中最大矩形面积：通过单调栈，可以找到每根柱子对应的左右边界，从而计算最大矩形面积。
温度问题：找出每一天后面多少天温度会升高。

单调栈的工作原理

遍历数组中的元素。
维护一个栈：栈中元素可能是数组中的索引或者具体的数值，取决于具体应用。
栈的操作规则
- 若栈为空，直接将当前元素入栈。
- 若栈不为空，判断当前元素与栈顶元素之间的关系，以决定是否出栈或入栈。

C++实现

以下是一个经典的单调栈应用的 C++ 代码示例：找出数组中每个元素右边的第一个比它大的元素。用一个单调递减栈维护

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> nextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1); // 初始化结果为 -1，表示如果没有更大的元素则返回 -1
    stack<int> st; // 栈中存储的是元素的索引

    for (int i = 0; i < n; ++i) {
        // 如果当前元素比栈顶索引指向的元素大，那么它就是该索引的下一个更大元素
        while (!st.empty() && nums[i] > nums[st.top()]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        // 将当前元素索引入栈
        st.push(i);
    }

    return result;
}

int main() {
    vector<int> nums = {2, 1, 2, 4, 3};
    vector<int> result = nextGreaterElement(nums);

    cout << "下一个更大元素为: ";
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }
    cout << endl;

    return 0;
}

代码详解

初始化：
- vector<int> result(n, -1);：用于存储每个元素右边的第一个比它大的元素，初始值为 -1。
- stack<int> st;：用于存储元素的索引，而不是元素的值。这是因为我们要在栈中找到对应索引的位置。
遍历数组：
- 使用 for (int i = 0; i < n; ++i) 遍历整个数组。
- 如果当前元素 nums[i] 大于栈顶的元素（通过索引 st.top() 获取），说明找到了栈顶元素右边的第一个更大元素，因此将 result[st.top()] = nums[i]。
- 继续 st.pop()，直到栈为空或栈顶元素不小于当前元素为止。
元素入栈：
- 每次处理完后，将当前元素的索引 i 入栈。

单调栈的时间复杂度

时间复杂度：O(n)，因为每个元素最多只会入栈和出栈一次。
空间复杂度：O(n)，用于存储栈和结果数组。

示例解析

考虑输入数组 nums = [2, 1, 2, 4, 3]：

遍历到 2，栈为空，入栈。
遍历到 1，1 小于栈顶元素 2，入栈。
遍历到 2，2 大于栈顶元素 1，result[1] = 2，弹出栈顶，2 仍小于栈顶元素 2，入栈。
遍历到 4，4 大于栈顶元素 2，result[2] = 4，弹出栈顶，继续对下一个栈顶元素 2，result[0] = 4，弹出栈顶。
遍历到 3，栈中只有一个元素 4，3 小于 4，入栈。
最终结果为 [4, 2, 4, -1, -1]。