• 单调栈

单调栈

单调栈是一种栈的特殊应用，用于解决一类需要在数据序列中找到特定元素的“最近较大/较小值”的问题。它的核心思想是通过保持栈内元素的单调性（即元素从栈底到栈顶按某种顺序排列），来简化和优化这些问题的解决。

单调栈的种类

• 单调递增栈：栈内元素从栈底到栈顶严格递增。也就是说，新加入栈的元素一定比栈顶元素大。用于查找每个元素左侧或者右侧第一个小于它的元素。
• 单调递减栈：栈内元素从栈底到栈顶严格递减。也就是说，新加入栈的元素一定比栈顶元素小。用于查找每个元素左侧或者右侧第一个大于它的元素。

单调栈的基本操作 在遍历元素序列时，对于每个元素 ${x}_{i}$

• 入栈操作：如果栈为空或者栈顶元素满足单调性（比当前元素小或大），则将当前元素入栈。
• 出栈操作：当栈顶元素不满足单调性（比当前元素小或大）时，将栈顶元素弹出，直到栈顶元素满足单调性为止。

单调栈的典型应用

• 找每个元素的左边或右边第一个比它大的/小的元素：
  • 通过单调递减栈可以快速找到每个元素右侧第一个大于它的元素。
  • 通过单调递增栈可以快速找到每个元素右侧第一个小于它的元素。
• 柱状图中的最大矩形面积问题：通过使用单调栈，可以在 𝑂(𝑛)时间内解决这个问题。

示例 假设有一个数组 [2, 1, 5, 6, 2, 3]，我们要找到每个元素右侧第一个小于它的元素。

初始化一个空的单调递增栈。 从左到右遍历数组元素： 2 入栈，栈为 [2]。 1 入栈前，发现 1 < 2，所以 2 出栈，1 入栈，栈为 [1]。 5 入栈，栈为 [1, 5]。 6 入栈，栈为 [1, 5, 6]。 2 入栈前，发现 2 < 6，所以 6 出栈，再发现 2 < 5，所以 5 也出栈，2 入栈，栈为 [1, 2]。 3 入栈，栈为 [1, 2, 3]。 根据这个过程，可以得出每个元素右侧第一个小于它的元素的对应位置。

单调栈通过这种方式有效地减少了不必要的比较，使得一些看似复杂的问题得到了简化和高效的解决。

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

std::vector<int> nextGreaterElement(const std::vector<int>& nums) {
    std::vector<int> result(nums.size(), -1); // 初始化结果数组，初始值为-1
    std::stack<int> st; // 栈中存储元素的下标

    for (int i = 0; i < nums.size(); ++i) {
        // 当栈不为空，且当前元素大于栈顶元素对应的数组中的元素
        while (!st.empty() && nums[i] > nums[st.top()]) {
            result[st.top()] = nums[i]; // 将当前元素作为栈顶元素的下一个更大元素
            st.pop(); // 弹出栈顶元素
        }
        st.push(i); // 将当前元素的下标入栈
    }

    return result; // 返回结果数组
}

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

    std::cout << "Next Greater Elements: ";
    for (int num : result) {
        std::cout << num << " ";
    }

    return 0;
}