当前位置：首页 > news >正文

力扣hot100，739每日温度(单调栈)详解

news 来源：原创 2025/6/9 10:20:57

时隔多久又遇到单调栈的题了，上次记得是接雨水的题，简单讲一下单调栈的适用场景和定义。

意义:看名字就知道单调栈是一个栈里面的数据是单调的。

解决问题:

单调栈主要用于解决需要**快速找到某个元素附近更大或更小的元素**的问题，其核心是通过维护栈内元素的单调性（递增或递减），将时间复杂度优化到 **O(n)**。以下是它的典型应用场景：

1. 寻找“下一个更大/更小元素
- 问题类型：给定一个数组，为每个元素找到其右侧/左侧第一个比它大或小的元素。
- 示例：
- [下一个更大元素 I](https://leetcode.cn/problems/next-greater-element-i/)
- [每日温度](https://leetcode.cn/problems/daily-temperatures/)
- 原理：
维护一个单调递减栈（栈顶最小），当新元素比栈顶大时，栈顶元素的下一个更大元素就是当前元素。

2. 处理区间极值或边界问题
- 问题类型：找到满足某种极值条件的子数组，或确定某个元素作为极值的最大区间。
- 示例
- [柱状图中的最大矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram/)：为每个柱子找到左右第一个比它矮的柱子，确定最大宽度。
-[接雨水](https://leetcode.cn/problems/trapping-rain-water/)：通过左右边界计算凹槽的储水量。
-原理：
单调递增栈（栈顶最大）可快速找到左右第一个更小的元素，从而确定当前元素作为区间最小值的边界。

3. 优化某些动态规划问题
- 问题类型：当动态规划的状态转移依赖前一个更大或更小的值时，可用单调栈加速查找。
-示例：
[子数组的最小值之和](https://leetcode.cn/problems/sum-of-subarray-minimums/)：利用单调栈快速找到每个元素作为最小值的贡献区间。

4. 字符串去重或字典序问题
问题类型：在字符串中删除重复字符或构造最小/最大字典序序列。
示例：
[去除重复字母](https://leetcode.cn/problems/remove-duplicate-letters/)：维护单调递增栈，保留最小字典序。

单调栈的选择规则
单调递增栈（栈底到栈顶递增）：用于找下一个更小的元素。
单调递减栈（栈底到栈顶递减）：用于找下一个更大的元素。

优势
- 时间复杂度 O(n)：每个元素最多入栈和出栈一次。
- 空间复杂度 O(n)：最坏情况下栈存储所有元素。

总结
当问题涉及**元素的邻近比较**、**区间极值边界**，或需要**维护序列的某种单调性**时，优先考虑单调栈。其核心是通过舍弃不必要的比较，高效定位目标元素。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n=temperatures.size();vector<int> answer(n,0);stack<int> m;for(int i=0;i<n;i++){while(!m.empty()){if(temperatures[i]>temperatures[m.top()]){int xx=m.top();answer[xx]=i-xx;m.pop();}else{break;}}m.push(i);}return answer;}
};

这个题就是一个单调递减栈，找右边更小的值

相关文章：