单调栈
一、简介
1.什么是单调栈？
单调栈的本质就是一个栈，只不过栈内元素都是单调递增/减的。
【tips】注意这里的递增递减指的是从栈顶到栈底是递增还是递减的。
单调栈是以空间换时间，时间复杂度为O(n)。
2.适用题型
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
3.单调栈的使用
使用单调栈主要有三个判断条件。
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
二、相关题目推荐
1.739. 每日温度
-
思路：本题就是要找元素右边第一个比自己大的元素的位置，此时就应该想到用单调栈了。在遍历时，用一个栈来记录右边第一个比当前元素大的元素的位置，始终维护栈为单调递增的。
public int[] dailyTemperatures(int[] temperatures) { //[73,74,75,71,69,72,76,73] Deque<Integer> stack=new ArrayDeque<>(); int[] res=new int[temperatures.length]; //单调栈内放的是元素位置 stack.push(0); //遍历数组同时维护一个单调递增栈 for(int i=1;i<temperatures.length;i++){ //当前元素小于等于栈顶元素，当前元素直接进栈 if(temperatures[i]<=temperatures[stack.peek()]){ stack.push(i); }else{ //当前元素大于栈顶位置，栈顶出栈，当前元素进栈 while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){ res[stack.peek()]=i-stack.peek(); stack.pop(); } stack.push(i); } } return res; }
2.496. 下一个更大元素 I
-
思路：这道题跟上一题差不多，区别就是这道题找的是右边第一个大的元素。再者一个绕的点就是如何建立num1和num2中元素的对应关系，这里我们用map来做一个映射记录。
public int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] ans=new int[nums1.length]; Arrays.fill(ans,-1); Map<Integer,Integer> map=new HashMap<>(); //记录num1中元素及对应下标 for(int i=0;i<nums1.length;i++){ map.put(nums1[i],i); } //单调递增栈 Deque<Integer> stack=new ArrayDeque<>(); stack.push(nums2[0]); for(int i=1;i<nums2.length;i++){ if(!stack.isEmpty()&&nums2[i]<=stack.peek()){ stack.push(nums2[i]); }else{ while(!stack.isEmpty()&&nums2[i]>stack.peek()){ //一定要保证map中有这个key再去记录ans! if(map.containsKey(stack.peek())){ ans[map.get(stack.peek())]=nums2[i]; } stack.pop(); } stack.push(nums2[i]); } } return ans; }
3.★503.下一个更大元素II
-
思路：首先要想清楚一个问题——★环形数组该怎么处理？
遇到环形数组的问题，之前做过可以再开辟一个2倍长度的新数组，然后放两个环形数组进去，这样就将环形数组变成了线性数组。比如说环形数组[1，2，3]，我们可以通过新数组[1，2，3，1，2，3]来模拟环形数组。这样做虽然可行，但是有两个问题：一是需要额外的空间，二是在构造这个新数组时会有额外的时间开销，所以一般不推荐。
但是这种思想还是很好的，★我们可以通过取模的方式，遍历两倍的原数组长度(i<2*arr.length)，来避免创建新数组解决环形数组的问题。public int[] nextGreaterElements(int[] nums) { int len=nums.length; int[] res=new int[len]; Arrays.fill(res,-1); Deque<Integer> stack=new ArrayDeque<>(); stack.push(0); for(int i=1;i<2*len;i++){//for循环长度是2倍环形数组长度！ //★取模为了让循环一直在原数组中进行 int idx=i%len; while(!stack.isEmpty()&&nums[idx]>nums[stack.peek()]){ res[stack.peek()]=nums[idx]; stack.pop(); } stack.push(idx); } return res; }
4.42. 接雨水
-
思路一：双指针优化的暴力解法。我们一列一列来看(左下图)，也就是求高，宽度固定是1。暴力解法就是一层for循环遍历每一列，另一层for循环找当前列的左边最高列和右边最高列，那么当前列能接的雨水高度=左右最高列中最小的高度 - 当前列高度，举个例子，比如求第四列雨水高度(如右下图)，它左边最高是第3列、高度2，右边最高是第7列、高度3，所以第四列雨水高度=2-1=1。
这样两层for循环的时间复杂度是O(n)。我们发现当前列雨水高度只与左/右边最高列有关，在找最高列时其实做了重复计算，对于当前列来说：- 当前列的左边最高列=max(当前列左邻居的左边最高列，左邻居高度)；
- 当前列的右边最高列=max(当前列右邻居的右边最高列，右邻居高度)；
public int trap(int[] height) { int len=height.length; int[] leftMax=new int[len]; int[] rightMax=new int[len]; //记录每一列的左边最高列高度 for(int i=0;i<len;i++){ if(i>0){ leftMax[i]=Math.max(leftMax[i-1],height[i-1]); }else{ leftMax[i]=0; } } //记录每一列的右边最高列高度 for(int i=len-1;i>=0;i--){ if(i<len-1){ rightMax[i]=Math.max(rightMax[i+1],height[i+1]); }else{ rightMax[i]=0; } } //求和 int sum=0; for(int i=1;i<len-1;i++){ int rain=Math.min(leftMax[i],rightMax[i])-height[i]; //★保证雨水为正！ if(rain>0){ sum+=rain; } } return sum; } -
思路二：单调栈。通过思路一可以发现，其实这道题就是找左边第一个比当前元素大的和右边第一个比当前元素大的，所以可以用单调栈来做。但是之前做都是求一边，这里左右两边都要找，我刚开始以为需要两次遍历，一次找右边、一次找左边。其实不用这样，我们是从左往右遍历数组，然后维护一个单调递增栈，这样的话在栈里面，栈顶元素的下一个栈元素就是他左边第一个比当前元素大的。所以相当于一次遍历就能找到左右两边的第一个最大值。
public int trap(int[] height) { Deque<Integer> stack=new ArrayDeque<>(); //因为单调栈是按行来算的，相当于记录了左右最高列之间的距离 stack.push(0); int sum=0; for(int i=1;i<height.length;i++){ while(!stack.isEmpty()&&height[i]>height[stack.peek()]){ int curIdx=stack.pop(); int h=0,w=0; if(!stack.isEmpty()){ h=Math.min(height[stack.peek()],height[i])-height[curIdx]; w=i-stack.peek()-1; } sum+=h*w; } //★这里左边第一个最高列和当前列相等我们选择把它加入栈里，后面计算高度时相等两数相减为0，面积就是0了，符合题意 stack.push(i); } return sum; }
5.84.柱状图中最大的矩形
接雨水是找左右两边第一个比当前大的，这道题是找左右两边第一个比当前小的。
-
思路一：双指针优化暴力解法。
注意！移动时不是每次--或++，这样就跟暴力没区别了，也没体现出我们创建的两个新数组的作用，而是利用前面/后面元素记录过的结果！class Solution { public int largestRectangleArea(int[] heights) { int len=heights.length; int[] leftMinIdx=new int[len]; int[] rightMinIdx=new int[len]; //记录左边第一个小于当前元素的下标 //注意第一个元素左边没有元素了，我们认为左边第一个比他小的下标是-1 leftMinIdx[0]=-1; for(int i=1;i<len;i++){ int t=i-1; //找左边第一个小于heights[i]的元素 while(t>=0&&heights[t]>=heights[i]){ //★★对暴力的优化，移动时t不是t--，而是利用了前面元素的leftMinIdx t=leftMinIdx[t]; } //记录下标 leftMinIdx[i]=t; } //记录右边第一个小于当前元素的下标 rightMinIdx[len-1]=len; for(int i=len-2;i>=0;i--){ int t=i+1; while(t<len&&heights[t]>=heights[i]){ t=rightMinIdx[t]; } //记录下标 rightMinIdx[i]=t; } //找最大面积 int res=0; for(int i=0;i<len;i++){ int h=heights[i]; int w=rightMinIdx[i]-leftMinIdx[i]-1; res=Math.max(res,h*w); } return res; } } -
思路二：采用单调递减栈，leftMin是栈中栈顶元素的下一个元素，rightMin是当前遍历到的元素，cur是栈顶元素。此时的★矩形h就是cur的高度★，w就是左右最小高度列的距离，所以面积=h×w。
★注意！我们要给原数组的前后各加一个0元素：
前面的0：为了计算原数组第一列的面积。
后面的0：因为如果原数组是升序的，比如[2，4，6，8]，那么加到单调递减栈里就是按单调递减的8 6 4 2的顺序入栈，就没法进行比较了，所以我们在原数组最后加一个0，即[2，4，6，8，0]，来保证既不影响结果，又能解决原数组是升序的情况。public int largestRectangleArea(int[] heights) { Deque<Integer> stack=new ArrayDeque<>(); //数组扩容，前后各加一个0 int[] newHeights=new int[heights.length+2]; for(int i=1;i<newHeights.length-1;i++){ newHeights[i]=heights[i-1]; } int s=newHeights[0]; stack.push(0); for(int i=1;i<newHeights.length;i++){ while(!stack.isEmpty()&&newHeights[i]<newHeights[stack.peek()]){ int h=newHeights[stack.pop()]; //此时的栈顶元素就是左边第一个比上面pop出去的小的 int w=i-stack.peek()-1; s=Math.max(s,h*w); } stack.push(i); } return s; }
