C++单调栈详解：查找下一个更大元素及应用

C++单调栈是一种特殊类型的栈，栈内元素按照某种顺序（递增或递减）排列。它可以高效地解决一些问题，例如查找数组中每个元素的下一个更大元素。

原理

单调栈的核心思想是维护一个递减（或递增）的序列。当遇到不满足单调性的元素时，弹出栈顶元素，直到满足单调性为止。这个过程中，弹出的元素和当前元素之间就形成了一种'下一个更大元素'的关系。

实现方法

在C++中，可以使用std::stack和std::pair来实现单调栈。栈中存储元素的索引，并根据元素的值来维护栈的单调性。

示例：查找下一个更大元素

以下代码演示了如何使用单调栈查找数组中每个元素的下一个更大元素：cpp#include #include #include

std::vector findNextGreater(const std::vector& nums) { std::vector result(nums.size(), -1); // 初始化结果数组为-1 std::stack stack; // 用于保存数组元素的索引

for (int i = 0; i < nums.size(); i++) {        // 如果栈非空且当前元素大于栈顶元素，则栈顶元素的下一个更大元素为当前元素        while (!stack.empty() && nums[i] > nums[stack.top()]) {            result[stack.top()] = nums[i];            stack.pop();        }        stack.push(i);  // 将当前元素索引压入栈中    }

return result;}

int main() { std::vector nums = {1, 3, 2, 4, 5, 3, 2, 1}; std::vector nextGreater = findNextGreater(nums);

std::cout << 'Next greater elements: ';    for (int num : nextGreater) {        std::cout << num << ' ';    }    std::cout << std::endl;

return 0;}

解释

findNextGreater函数接收一个整数数组作为输入，返回一个相同长度的数组，表示每个元素的下一个更大元素。2. 使用std::stack创建一个空栈，用于存储数组元素的索引。3. 遍历输入数组，对于每个元素： - 如果栈非空且当前元素大于栈顶元素，则栈顶元素的下一个更大元素就是当前元素，更新结果数组，并将栈顶元素弹出。重复此过程，直到栈为空或当前元素小于等于栈顶元素。 - 将当前元素的索引压入栈中。4. 返回结果数组。

应用场景

单调栈除了可以查找下一个更大元素外，还可以应用于许多其他问题，例如：

查找下一个更小元素- 查找最大矩形面积（直方图问题）- 股票交易问题

希望本文能够帮助你理解和使用C++单调栈！