单调栈

学习链接:

刷题论 02|单调栈真没你想的那么难_哔哩哔哩_bilibili

单调栈【基础算法精讲 26】_哔哩哔哩_bilibili

一、单调栈的原理

​ 单调栈是一种特殊的栈结构,其核心在于维护栈内元素的单调性(递增或递减),用于高效解决序列中元素的 最近邻大小关系 问题。其核心原理如下:

  1. 单调性维护:在遍历数组时,若当前元素破坏栈的单调性(例如,在单调递减栈中当前元素比栈顶大),则弹出栈顶元素,直到满足单调性再入栈。这一过程使得栈内元素保持单调性,从而快速确定每个元素的最近邻更大或更小元素
  2. 方向选择:
    • 单调递增栈栈底到栈顶元素递增,用于寻找当前元素的下一个更小元素
    • 单调递减栈栈底到栈顶元素递减,用于寻找当前元素的下一个更大元素

二、深究

​ 单调栈的方向选择(递增或递减)与寻找元素的下一个更大或更小值之间的关联性,源于其维护单调性的规则和遍历顺序的配合。以下是具体分析:

2.1 单调递增栈:寻找下一个更小元素

定义:栈底到栈顶元素递增,即栈顶元素是栈中最大的元素。
核心规则:新元素入栈时,需弹出所有比当前元素大的栈顶元素。【!!!】:whale:
逻辑推导

  1. 维护单调性:当新元素比栈顶元素小时,必须弹出栈顶元素以保持递增性。此时,新元素即为被弹出元素的“右侧第一个更小元素”。
  2. 应用场景:
    • 左侧第一个更小元素:从左到右遍历,栈中保留的是比当前元素大的值。新元素入栈时,栈顶元素即为当前元素的左侧第一个更小值。
    • 右侧第一个更小元素:从右到左遍历,新元素会触发比它大的栈顶元素弹出,被弹出元素的右侧第一个更小值即当前元素。

示例
数组 [3, 1, 4, 2] 中,若从左到右遍历并维护递增栈:

  • 元素 1 入栈时,会弹出 3,此时 13 的右侧第一个更小元素。

2.2 单调递减栈:寻找下一个更大元素

定义:栈底到栈顶元素递减,即栈顶元素是栈中最小的元素。
核心规则:新元素入栈时,需弹出所有比当前元素小的栈顶元素。
逻辑推导

  1. 维护单调性:当新元素比栈顶元素大时,必须弹出栈顶元素以保持递减性。此时,新元素即为被弹出元素的“右侧第一个更大元素”。
  2. 应用场景:
    • 左侧第一个更大元素:从左到右遍历,栈中保留的是比当前元素小的值。新元素入栈时,栈顶元素即为当前元素的左侧第一个更大值。
    • 右侧第一个更大元素:从右到左遍历,新元素触发比它小的栈顶元素弹出,被弹出元素的右侧第一个更大值即当前元素。

示例
数组 [2, 1, 4, 3] 中,若从右到左遍历并维护递减栈:

  • 元素 3 入栈后,元素 4 触发 3 弹出,此时 43 的右侧第一个更大元素。

方向选择的关键点

  1. 单调性与目标关系:
    • 单调递增栈的弹出条件(当前元素更小)直接关联“下一个更小值”的查找。
    • 单调递减栈的弹出条件(当前元素更大)直接关联“下一个更大值”的查找。
  2. 遍历顺序的影响:
    • 从左到右遍历时,栈中保存的是已处理元素的单调序列,用于确定左侧关系。
    • 从右到左遍历时,栈中保存的是未处理元素的单调序列,用于确定右侧关系。

总结

  • 单调递增栈通过维护递增性,确保每次弹出操作能确定被弹出元素的“更小值”位置。
  • 单调递减栈通过维护递减性,确保每次弹出操作能确定被弹出元素的“更大值”位置。
  • 遍历方向(左到右或右到左)决定了是找左侧还是右侧的关系

2.3 单调栈遍历方向与边界查找的深度解析

​ 单调栈的核心在于通过维护栈内元素的单调性,高效定位元素的最近邻大小关系。其遍历方向(左→右或右→左)与目标边界(左/右侧第一个更大/更小元素)的组合会直接影响实现逻辑和栈的单调性选择。以下是具体分析:

一、方向与单调性的关联规则

根据搜索结果 ,可总结以下规则:

  1. 单调性决定查找目标类型:
    • 单调递增栈(栈顶到栈底递增):用于查找 更小的元素
    • 单调递减栈(栈顶到栈底递减):用于查找 更大的元素
  2. 遍历方向决定边界类型:
    • 从左到右遍历:主要用于处理 左侧边界实时更新右侧边界
    • 从右到左遍历:主要用于处理 右侧边界预处理左侧边界

二、四种典型场景的对比分析

1. 寻找左侧第一个更小元素
  • 方向选择:从左到右遍历。
  • 单调性:递增栈。
  • 实现逻辑:【栈顶到栈底递增】
    • 每个元素入栈前,弹出栈顶所有 ≥ 当前元素的元素,此时栈顶即为左侧第一个更小的元素。
    • 示例:数组[3,4,2,7,5] 中,元素2的左侧第一个更小元素是3(需从左到右维护递增栈)。
  • 复杂度:时间复杂度 𝑂(𝑛)O(n),空间复杂度 𝑂(𝑛)O(n)。
2. 寻找右侧第一个更大元素
  • 方向选择

    两种方式均可行

    ,但逻辑不同:

    • 从左到右遍历(推荐)

      • 单调性:递减栈。

      • 实现逻辑

        :当遇到更大元素时,弹出栈顶元素并记录其右侧更大元素索引(如 LeetCode 739 每日温度问题)

        4

        5

    • 从右到左遍历

      • 单调性:递减栈。
      • 实现逻辑:栈中保存右侧元素的候选值,当前元素入栈时栈顶即为右侧第一个更大元素。
  • 对比

    :从左到右遍历通过弹出时更新结果,从右到左遍历通过压栈时记录结果

    1

    5

3. 寻找右侧第一个更小元素
  • 方向选择从右到左遍历

  • 单调性:递增栈。

  • 实现逻辑

    • 栈中保存右侧元素的候选值,当前元素入栈前弹出所有 ≥ 当前元素的元素,此时栈顶即为右侧第一个更小元素。

    • 示例

      :柱状图最大矩形问题中,计算每个柱子右侧第一个更矮的位置需从右到左维护递增栈

      6

4. 寻找左侧第一个更大元素
  • 方向选择从左到右遍历

  • 单调性:递减栈。

  • 实现逻辑

    • 每个元素入栈前弹出所有 ≤ 当前元素的元素,栈顶即为左侧第一个更大元素。

    • 示例

      :数组

      1
      [2,7,5,4,6]

      中,元素

      1
      6

      的左侧第一个更大元素是

      1
      7

      (需维护递减栈)

      1

三、遍历方向的核心差异

  1. 信息利用方式

    • 从左到右遍历:栈中保存的是 已遍历元素的左侧信息,适合实时处理左侧或动态更新右侧边界。

    • 从右到左遍历

      :栈中保存的是

      未遍历元素的右侧信息

      ,适合预处理右侧边界或批量处理左侧边界

      5

      6

  2. 结果更新时机

    • 从左到右遍历时,右侧边界的答案在 元素弹出栈时更新(如每日温度问题)。

    • 从右到左遍历时,右侧边界的答案在

      元素压栈时确定

      (如柱状图右侧边界)

      4

      6

  3. 代码复杂度

    • 从左到右遍历通常更直观,适合动态更新结果。

    • 从右到左遍历可能需要预处理数组或额外处理栈的初始状态

      2

      5

四、经典问题对比(以 LeetCode 739 为例)

  • 从左到右遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Cppvector<int> dailyTemperatures(vector<int>& T) {
    stack<int> stk;
    vector<int> ans(T.size(), 0);
    for (int i = 0; i < T.size(); i++) {
    while (!stk.empty() && T[i] > T[stk.top()]) {
    int pre = stk.top();
    ans[pre] = i - pre;
    stk.pop();
    }
    stk.push(i);
    }
    return ans;
    }
    • 逻辑

      :维护递减栈,弹出时更新右侧更大元素的索引

      4

  • 从右到左遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Cppvector<int> dailyTemperatures(vector<int>& T) {
    stack<int> stk;
    vector<int> ans(T.size(), 0);
    for (int i = T.size() - 1; i >= 0; i--) {
    while (!stk.empty() && T[i] >= T[stk.top()])
    stk.pop();
    ans[i] = stk.empty() ? 0 : stk.top() - i;
    stk.push(i);
    }
    return ans;
    }
    • 逻辑

      :维护递减栈,压栈时确定右侧更大元素的索引

      5

五、总结

  1. 单调性选择:优先根据目标类型(更大/更小)确定单调递增或递减栈。

  2. 方向选择

    • 左侧边界:优先从左到右遍历。
    • 右侧边界:可灵活选择方向,但需注意更新逻辑的差异。
  3. 性能与实现

    :两种方向均能达到

    𝑂(𝑛)O(n)

    时间复杂度,但具体实现需结合问题特点(如是否需要预处理边界)

    1

    6

三、适用场景

​ 单调栈常用于以下问题(时间复杂度通常为 **𝑂(𝑛)**):

  1. 下一个更大/更小元素(NGE/NGSE):例如,给定数组,为每个元素找到右侧第一个比它大的元素。
  2. 柱状图最大矩形面积:通过单调栈快速确定每个高度能扩展的最大左右边界。
  3. 滑动窗口极值优化:结合单调队列,维护窗口内的极值信息。
  4. 子数组指标优化:如找到子数组的最小值与子数组和的乘积最大值,需确定每个元素作为最小值的最大左右边界。
  5. 字符串去重:在保证字典序最小的前提下删除重复字符。

四、C++版单调栈的实现与示例代码

一、基础实现(寻找左侧第一个更小元素)

问题:给定数组,输出每个元素左侧第一个比它小的元素,不存在则输出 -1
代码实现(基于网页3的模板):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <stack>
using namespace std;

int main() {
stack<int> stk;
int n;
scanf("%d", &n);
while (n--) {
int x;
scanf("%d", &x);
// 维护单调递增栈(栈顶到栈底递增)
while (!stk.empty() && stk.top() >= x) {
stk.pop();
}
// 输出结果
if (stk.empty()) {
printf("-1 ");
} else {
printf("%d ", stk.top());
}
stk.push(x);
}
return 0;
}

说明

  • 维护单调递增栈,确保栈顶元素始终是左侧最近的更小值。
  • 遍历时,若当前元素小于栈顶,则不断弹出栈顶元素直至满足单调性,此时栈顶即为左侧第一个更小元素。
  • 适用场景:实时处理流式数据,适用于数据规模较大(如𝑛≤105n≤105)的场景。

二、模板类实现(通用型单调栈)

代码实现(基于网页1的模板类封装):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stack>
using namespace std;

template <typename T>
class MonotonicStack : public stack<T> {
public:
using stack<T>::empty;
using stack<T>::top;
using stack<T>::pop;

void push(T val) {
// 维护单调递减栈(栈顶到栈底递减)
while (!empty() && val >= top()) {
pop();
}
stack<T>::push(val);
}
};

说明

  • 继承自 std::stack,通过模板支持泛型。

  • push 时自动维护栈的单调性(此处为递减栈),可自定义条件(如 val <= top() 改为递增栈)。

  • 适用场景

    :需多次复用单调栈逻辑的工程场景,或需要封装回调函数处理弹出元素的高级需求。

三、经典问题:每日温度(LeetCode 739)

问题:计算每天需要等待几天才能遇到更高温度。
代码实现(基于网页5的反向遍历法):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
#include <stack>
using namespace std;

vector<int> dailyTemperatures(vector<int>& temps) {
int n = temps.size();
stack<int> stk;
vector<int> ans(n, 0);
for (int i = n - 1; i >= 0; i--) {
// 维护单调递减栈(栈顶到栈底递减)
while (!stk.empty() && temps[i] >= temps[stk.top()]) {
stk.pop();
}
if (!stk.empty()) {
ans[i] = stk.top() - i;
}
stk.push(i);
}
return ans;
}

说明

  • 反向遍历:从右向左遍历数组,栈中存储的是可能的未来高温天数索引。

  • 时间复杂度 𝑂(𝑛)O(n),空间复杂度 𝑂(𝑛)O(n)。

  • 适用场景

    :需要高效计算每个元素的“下一个更大元素”索引的场景。

四、进阶应用:处理重复元素(左右边界扩展)

问题:存在重复元素的数组中,找到每个元素作为最小值时的左右边界。
代码实现(参考网页6的左右栈处理):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<long long> maxSumOfHeights(vector<int>& maxHeights) {
int n = maxHeights.size();
vector<long long> left(n), right(n);
stack<int> stk;

// 处理左边界
for (int i = 0; i < n; i++) {
while (!stk.empty() && maxHeights[i] <= maxHeights[stk.top()]) {
stk.pop();
}
if (stk.empty()) {
left[i] = (long long)maxHeights[i] * (i + 1);
} else {
left[i] = left[stk.top()] + (long long)maxHeights[i] * (i - stk.top());
}
stk.push(i);
}

// 处理右边界(类似反向处理)
// ...

return result;
}

说明

  • 双栈法分别处理左右边界,栈中保存索引,计算每个元素作为极值时的最大扩展范围。
  • 适用场景:复杂极值问题(如柱状图最大矩形、美丽塔问题)。

五、总结

  1. 基础模板:直接使用std::stackvector维护单调性,适用于简单场景。
  2. 反向遍历:优化“下一个更大元素”类问题,避免正向遍历的多次回溯。
  3. 泛型封装:通过模板类实现可复用的单调栈结构。
  4. 边界扩展:结合左右栈处理复杂极值问题。