单调栈学习
单调栈
1）单调递减栈，栈中记录下标，当元素下标从栈中抛出时，计算最终的答案。
- 每日温度
请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。
如果气温在这之后都不会升高，请在该位置用 0 来代替。
2)问题中分析需要找最短子数组，因此要确定数组的左右边界，升序排序其实是有在暗示升序单调栈的方法。最难考虑就是两个边界应该如何确定，通过正向遍历升序单调栈可以确定左边界，反向遍历通过降序单调栈确定右边界。
- 最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
739. 每日温度
([https://leetcode-cn.com/problems/daily-temperatures/](https://leetcode-cn.com/problems/daily-temperatures/) )
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
int previousIndex = s.top();
ans[previousIndex] = i - previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};
581. 最短无序连续子数组
https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
stack<int> stk1,stk2;
int n = nums.size();
int mn = n+1,mx = -1;
for(int i = 0;i < n; i++){
while(!stk1.empty() && nums[stk1.top()] > nums[i]){
mn = min(stk1.top(),mn);
stk1.pop();
}
stk1.push(i);
}
for(int j = n - 1;j >= 0;j--){
while(!stk2.empty() && nums[stk2.top()] < nums[j]){
mx = max(mx,stk2.top());
stk2.pop();
}
stk2.push(j);
}
return mx > mn ? mx-mn+1 : 0;
}
};