前言
折磨的死去活来的动态规划终于结束啦,今天秋秋给大家带来两题非常经典的单调栈问题,可能你不清楚单调栈是什么,可以用来解决什么问题,今天我们就来一步一步的逐渐了解单调栈,到能够灵活使用单调栈.注意以下讲解中，顺序的描述为 从栈头到栈底的顺序
什么时候用单调栈?
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。这种情况我们使用暴力的两层for循环很明显是O(n^2)的时间复杂度.
那么单调栈的原理是什么呢？
原理就是用空间来换时间,用一个辅助栈来完成了一次循环做的事情,也就是记录下了前面已经遍历过的元素.更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。
注意点
1.明确是单调递增栈还是单调递减栈
如果求一个元素右边第一个比他大的元素,就使用递增栈,如果是求比他小的元素就使用递减栈
当然左边也一样
2.明确单调栈里面放的是啥,表示什么意思
模拟
下面我们举个例子来直观感受一下单调栈的执行过程
首先这题肯定是一个单调增栈
接下来我们用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析，输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
1.首先先将第一个遍历元素加入单调栈(放入的是下标,因为很多情况下需要使用下标更好操作一点)
2.判断目前遍历的元素和栈顶元素的大小进行比较,有三种情况,大于等于小于
此时小于和等于的情况是一样的,我们直接将其入栈即可,要是大于我们就让栈顶元素出栈,一直比较,让所有比我目前遍历的元素小的元素都出栈,此时出栈的时候就是收割结果的时候,直接让当前元素和栈顶元素作差存入结果数组即可,如此循环往复即可得到答案.
有人说栈里面最后还会存有元素怎么办??
无需处理
最后无需处理的原因是因为初始化的时候已经确定了这种没有结果的默认值
LeetCode T739 每日温度
题目链接:739. 每日温度 - 力扣（LeetCode）
题目思路:
利用上述单调栈的思路
我们在单调栈中存下标,进行比较的时候如果小于等于nums[栈顶元素]直接让其入栈,大于的话就将栈顶元素作为结果数组的下标,返回两者差值,切记:要将当前元素继续比较,直到不能比较为止,所以这里用的是while而不是if(也要记得不能比之后将目前元素入栈)
最后返回结果数组即可
题目代码:
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack<Integer> st = new Stack<>();
st.push(0);
for(int i = 1;i<temperatures.length;i++){
if(!st.isEmpty()&&temperatures[i]<=temperatures[st.peek()]){
st.push(i);
}else{
while(!st.isEmpty()&&temperatures[i]>temperatures[st.peek()]){
res[st.peek()] = i - st.peek();
st.pop();
}
st.push(i);
}
}
return res;
}
}LeetCode T496 下一个最大元素I
题目链接:496. 下一个更大元素 I - 力扣（LeetCode）
题目思路:
相比于上面的题目,本题的意思是nums1对应在nums2中的相同数值的元素,求nums2中比此元素大的第一个元素的值,并返回长度和nums1相同,各个元素的求值结果.找不到返回-1
这里我们用示例2来理解一下题意,避免曲解题意
nums1 = [2,4]
nums2 = [1,2,3,4]
这里nums1的元素2对应在nums2中的2,其中第一个比他大的元素是3,所以res[0] = 3同理4在nums2中找不到比他还大的元素了,返回的就是res[1] = -1
这题的关键难点就是将这两个数组联系起来,我们可以使用map的方式将两个元素联系起来
这里由于元素都是唯一存在的,所以我们可以用map遍历第一个数组,key对应元素,value对应下标,这样我们在nums2中找到元素之后就可以利用这个map来得到其对应元素在nums1中的下标了,从而填入我们的结果数组中返回.
题目代码:
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> st = new Stack<>();
Map<Integer,Integer> map = new HashMap<>();
int[] res= new int[nums1.length];
Arrays.fill(res,-1);
for(int i = 0;i<nums1.length;i++){
map.put(nums1[i],i);
}
st.push(0);
for(int i = 1;i<nums2.length;i++){
if(!st.isEmpty() && nums2[i]<=nums2[st.peek()]){
st.push(i);
}
else{
while(!st.isEmpty() && nums2[i]>nums2[st.peek()]){
if(map.containsKey(nums2[st.peek()])){
Integer index = map.get(nums2[st.peek()]);
res[index] = nums2[i];
}
st.pop();
}
st.push(i);
}
}
return res;
}
}
