c++中如何实现单调栈_c++单调栈实现方法-C++-PHP中文网

c++中如何实现单调栈_c++单调栈实现方法

冰火之心

发布： 2025-10-07 10:29:02

原创

289人浏览过

单调栈是保持元素单调递增或递减的栈结构，用于解决下一更大/更小元素等问题。1. 分为单调递增栈和单调递减栈，通过在入栈前弹出破坏顺序的元素维护单调性。2. 使用std::stack实现时通常存储数组下标，便于访问原数组和计算距离。3. 在寻找每个元素右侧第一个更小元素时采用单调递减栈，通过while循环持续弹出大于等于当前元素的栈顶元素。4. 寻找下一个更大元素则使用单调递增栈，调整比较条件为大于关系即可。5. 每个元素最多入栈出栈一次，时间复杂度为O(n)。核心在于理解单调性维护机制并应用于最近更大或更小元素问题。

c++中如何实现单调栈_c++单调栈实现方法

单调栈是一种特殊的栈结构，其内部元素始终保持单调递增或单调递减的顺序。它常用于解决“下一个更大元素”、“最大矩形面积”等一类问题。在C++中，我们可以借助std::stack来高效实现单调栈。

什么是单调栈

单调栈分为两种：

单调递增栈：从栈底到栈顶元素值递增（允许相等为非严格递增）
单调递减栈：从栈底到栈顶元素值递减（允许相等为非严格递减）

维护单调性的关键是在入栈前，将破坏顺序的元素从栈顶弹出。

使用 std::stack 实现单调递减栈

下面以单调递减栈为例，实现在数组中找到每个元素右边第一个更小的元素（Next Smaller Element）。

立即学习“C++免费学习笔记（深入）”；

表单大师AI

一款基于自然语言处理技术的智能在线表单创建工具，可以帮助用户快速、高效地生成各类专业表单。

查看详情

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

std::vector<int> nextSmallerElement(const std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> result(n, -1); // 默认值为-1，表示右侧无更小元素
    std::stack<int> stk; // 存储的是索引

    for (int i = 0; i < n; ++i) {
        // 维护单调递减：当前元素小于栈顶对应值时，更新结果
        while (!stk.empty() && arr[i] < arr[stk.top()]) {
            result[stk.top()] = arr[i];
            stk.pop();
        }
        stk.push(i);
    }

    return result;
}

int main() {
    std::vector<int> arr = {4, 2, 6, 1, 3};
    std::vector<int> res = nextSmallerElement(arr);

    for (int val : res) {
        std::cout << val << " ";
    }
    // 输出: 2 1 1 -1 -1
    return 0;
}

实现单调递增栈（找下一个更大元素）

只需调整比较方向即可实现单调递增栈，用于找每个元素右边第一个更大的元素。

std::vector<int> nextGreaterElement(const std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> result(n, -1);
    std::stack<int> stk;

    for (int i = 0; i < n; ++i) {
        // 当前元素大于栈顶元素时，更新结果
        while (!stk.empty() && arr[i] > arr[stk.top()]) {
            result[stk.top()] = arr[i];
            stk.pop();
        }
        stk.push(i);
    }

    return result;
}