无标题
单调栈
学习链接:
刷题论 02|单调栈真没你想的那么难_哔哩哔哩_bilibili
一、单调栈的原理
单调栈是一种特殊的栈结构,其核心在于维护栈内元素的单调性(递增或递减),用于高效解决序列中元素的 最近邻大小关系 问题。其核心原理如下:
- 单调性维护:在遍历数组时,若当前元素破坏栈的单调性(例如,在单调递减栈中当前元素比栈顶大),则弹出栈顶元素,直到满足单调性再入栈。这一过程使得栈内元素保持单调性,从而快速确定每个元素的最近邻更大或更小元素
- 方向选择:
- 单调递增栈:栈底到栈顶元素递增,用于寻找当前元素的下一个更小元素。
- 单调递减栈:栈底到栈顶元素递减,用于寻找当前元素的下一个更大元素。
二、深究
单调栈的方向选择(递增或递减)与寻找元素的下一个更大或更小值之间的关联性,源于其维护单调性的规则和遍历顺序的配合。以下是具体分析:
2.1 单调递增栈:寻找下一个更小元素
定义:栈底到栈顶元素递增,即栈顶元素是栈中最大的元素。
核心规则:新元素入栈时,需弹出所有比当前元素大的栈顶元素。【!!!】:whale:
逻辑推导:
- 维护单调性:当新元素比栈顶元素小时,必须弹出栈顶元素以保持递增性。此时,新元素即为被弹出元素的“右侧第一个更小元素”。
- 应用场景:
- 左侧第一个更小元素:从左到右遍历,栈中保留的是比当前元素大的值。新元素入栈时,栈顶元素即为当前元素的左侧第一个更小值。
- 右侧第一个更小元素:从右到左遍历,新元素会触发比它大的栈顶元素弹出,被弹出元素的右侧第一个更小值即当前元素。
示例:
数组 [3, 1, 4, 2]
中,若从左到右遍历并维护递增栈:
- 元素
1
入栈时,会弹出3
,此时1
是3
的右侧第一个更小元素。
2.2 单调递减栈:寻找下一个更大元素
定义:栈底到栈顶元素递减,即栈顶元素是栈中最小的元素。
核心规则:新元素入栈时,需弹出所有比当前元素小的栈顶元素。
逻辑推导:
- 维护单调性:当新元素比栈顶元素大时,必须弹出栈顶元素以保持递减性。此时,新元素即为被弹出元素的“右侧第一个更大元素”。
- 应用场景:
- 左侧第一个更大元素:从左到右遍历,栈中保留的是比当前元素小的值。新元素入栈时,栈顶元素即为当前元素的左侧第一个更大值。
- 右侧第一个更大元素:从右到左遍历,新元素触发比它小的栈顶元素弹出,被弹出元素的右侧第一个更大值即当前元素。
示例:
数组 [2, 1, 4, 3]
中,若从右到左遍历并维护递减栈:
- 元素
3
入栈后,元素4
触发3
弹出,此时4
是3
的右侧第一个更大元素。
方向选择的关键点
- 单调性与目标关系:
- 单调递增栈的弹出条件(当前元素更小)直接关联“下一个更小值”的查找。
- 单调递减栈的弹出条件(当前元素更大)直接关联“下一个更大值”的查找。
- 遍历顺序的影响:
- 从左到右遍历时,栈中保存的是已处理元素的单调序列,用于确定左侧关系。
- 从右到左遍历时,栈中保存的是未处理元素的单调序列,用于确定右侧关系。
总结
- 单调递增栈通过维护递增性,确保每次弹出操作能确定被弹出元素的“更小值”位置。
- 单调递减栈通过维护递减性,确保每次弹出操作能确定被弹出元素的“更大值”位置。
- 遍历方向(左到右或右到左)决定了是找左侧还是右侧的关系
2.3 单调栈遍历方向与边界查找的深度解析
单调栈的核心在于通过维护栈内元素的单调性,高效定位元素的最近邻大小关系。其遍历方向(左→右或右→左)与目标边界(左/右侧第一个更大/更小元素)的组合会直接影响实现逻辑和栈的单调性选择。以下是具体分析:
一、方向与单调性的关联规则
根据搜索结果 ,可总结以下规则:
- 单调性决定查找目标类型:
- 单调递增栈(栈顶到栈底递增):用于查找 更小的元素。
- 单调递减栈(栈顶到栈底递减):用于查找 更大的元素。
- 遍历方向决定边界类型:
- 从左到右遍历:主要用于处理 左侧边界 或 实时更新右侧边界。
- 从右到左遍历:主要用于处理 右侧边界 或 预处理左侧边界。
二、四种典型场景的对比分析
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
。
三、遍历方向的核心差异
信息利用方式
:
从左到右遍历:栈中保存的是 已遍历元素的左侧信息,适合实时处理左侧或动态更新右侧边界。
从右到左遍历
:栈中保存的是
未遍历元素的右侧信息
,适合预处理右侧边界或批量处理左侧边界
5
6
。
结果更新时机
:
从左到右遍历时,右侧边界的答案在 元素弹出栈时更新(如每日温度问题)。
从右到左遍历时,右侧边界的答案在
元素压栈时确定
(如柱状图右侧边界)
4
6
。
代码复杂度
:
从左到右遍历通常更直观,适合动态更新结果。
从右到左遍历可能需要预处理数组或额外处理栈的初始状态
2
5
。
四、经典问题对比(以 LeetCode 739 为例)
从左到右遍历:
1
2
3
4
5
6
7
8
9
10
11
12
13Cppvector<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
11Cppvector<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
。
五、总结
单调性选择:优先根据目标类型(更大/更小)确定单调递增或递减栈。
方向选择
:
- 左侧边界:优先从左到右遍历。
- 右侧边界:可灵活选择方向,但需注意更新逻辑的差异。
性能与实现
:两种方向均能达到
𝑂(𝑛)O(n)
时间复杂度,但具体实现需结合问题特点(如是否需要预处理边界)
1
6
三、适用场景
单调栈常用于以下问题(时间复杂度通常为 **𝑂(𝑛)**):
- 下一个更大/更小元素(NGE/NGSE):例如,给定数组,为每个元素找到右侧第一个比它大的元素。
- 柱状图最大矩形面积:通过单调栈快速确定每个高度能扩展的最大左右边界。
- 滑动窗口极值优化:结合单调队列,维护窗口内的极值信息。
- 子数组指标优化:如找到子数组的最小值与子数组和的乘积最大值,需确定每个元素作为最小值的最大左右边界。
- 字符串去重:在保证字典序最小的前提下删除重复字符。
四、C++版单调栈的实现与示例代码
一、基础实现(寻找左侧第一个更小元素)
问题:给定数组,输出每个元素左侧第一个比它小的元素,不存在则输出 -1
。
代码实现(基于网页3的模板):
1 |
|
说明:
- 维护单调递增栈,确保栈顶元素始终是左侧最近的更小值。
- 遍历时,若当前元素小于栈顶,则不断弹出栈顶元素直至满足单调性,此时栈顶即为左侧第一个更小元素。
- 适用场景:实时处理流式数据,适用于数据规模较大(如𝑛≤105n≤105)的场景。
二、模板类实现(通用型单调栈)
代码实现(基于网页1的模板类封装):
1 |
|
说明:
继承自
std::stack
,通过模板支持泛型。在
push
时自动维护栈的单调性(此处为递减栈),可自定义条件(如val <= top()
改为递增栈)。适用场景
:需多次复用单调栈逻辑的工程场景,或需要封装回调函数处理弹出元素的高级需求。
三、经典问题:每日温度(LeetCode 739)
问题:计算每天需要等待几天才能遇到更高温度。
代码实现(基于网页5的反向遍历法):
1 |
|
说明:
反向遍历:从右向左遍历数组,栈中存储的是可能的未来高温天数索引。
时间复杂度 𝑂(𝑛)O(n),空间复杂度 𝑂(𝑛)O(n)。
适用场景
:需要高效计算每个元素的“下一个更大元素”索引的场景。
四、进阶应用:处理重复元素(左右边界扩展)
问题:存在重复元素的数组中,找到每个元素作为最小值时的左右边界。
代码实现(参考网页6的左右栈处理):
1 | vector<long long> maxSumOfHeights(vector<int>& maxHeights) { |
说明:
- 双栈法分别处理左右边界,栈中保存索引,计算每个元素作为极值时的最大扩展范围。
- 适用场景:复杂极值问题(如柱状图最大矩形、美丽塔问题)。
五、总结
- 基础模板:直接使用
std::stack
或vector
维护单调性,适用于简单场景。 - 反向遍历:优化“下一个更大元素”类问题,避免正向遍历的多次回溯。
- 泛型封装:通过模板类实现可复用的单调栈结构。
- 边界扩展:结合左右栈处理复杂极值问题。