单调栈c++

### 单调栈算法的 C++ 实现 单调栈是一种特殊的栈结构，其核心特性在于栈中的元素始终保持有序（递增或递减）。这种数据结构通常用于解决涉及最近最小值或最大值的问题。 #### 单调栈的核心作用 单调栈的主要用途是在数组中快速找到某个位置左侧或右侧第一个小于或大于当前值的位置。通过维护一个单调性质的栈，可以显著降低时间复杂度至 \(O(n)\)[^1]。 --- #### 数组无重复值时的单调栈实现 当数组中的元素不包含重复值时，可以通过如下方式构建单调栈： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> nums(n); for (auto& num : nums) cin >> num; vector<int> result(n, -1); // 存储结果，默认为-1表示不存在 vector<int> stack; // 使用向量模拟栈 for (int i = 0; i < n; ++i) { while (!stack.empty() && nums[stack.back()] >= nums[i]) { stack.pop_back(); // 维护栈的单调性 } if (!stack.empty()) { result[i] = stack.back(); // 找到左边第一个较小值对应的索引 } stack.push_back(i); // 当前索引入栈 } for (const auto& res : result) cout << res << " "; } ``` 上述代码实现了寻找每个元素左侧第一个比它小的元素的功能[^2]。 --- #### 数组有重复值时的单调栈实现 如果数组中有重复值，则需要调整逻辑以处理相等情况下的行为。以下是改进后的版本： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> nums(n); for (auto& num : nums) cin >> num; vector<int> result(n, -1); // 默认初始化为-1 vector<int> stack; // 向量作为栈 for (int i = 0; i < n; ++i) { while (!stack.empty() && nums[stack.back()] > nums[i]) { stack.pop_back(); // 移除不符合条件的元素 } if (!stack.empty()) { result[i] = stack.back(); // 记录左侧第一个不大于它的索引 } stack.push_back(i); // 将当前索引进栈 } for (const auto& res : result) cout << res << " "; } ``` 此代码适用于存在重复值的情况，并能正确返回所需的结果[^3]。 --- #### 时间与空间复杂度分析 - **时间复杂度**: 每个元素最多被压入和弹出栈各一次，因此整体的时间复杂度为 \(O(n)\)[^4]。 - **空间复杂度**: 需要额外的空间存储栈以及结果数组，故空间复杂度为 \(O(n)\)。 --- #### 应用场景举例 单调栈常应用于以下问题： 1. 寻找数组中每个元素左侧/右侧的第一个更小或更大的数。 2. 解决接雨水问题（LeetCode 第 42 题），利用单调栈优化动态规划方法。 3. 处理股票价格波动问题，找出某一天之前最后一个小于等于当天的价格。 ---