java算法day59 | 单调栈part02 ● 503.下一个更大元素II ● 42. 接雨水

本文主要是介绍java算法day59 | 单调栈part02 ● 503.下一个更大元素II ● 42. 接雨水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

503.下一个更大元素II

在这里插入图片描述

思路： 相比于单纯寻找下一个最大元素，要遍历两边数组，注意i%nums.length。

class Solution {public int[] nextGreaterElements(int[] nums) {int[] res=new int[nums.length];for(int i=0;i<res.length;i++){res[i]=-1;}Deque<Integer> stack=new LinkedList<>();stack.push(0);for(int i=0;i<nums.length*2;i++){if(nums[i%nums.length]<=nums[stack.peek()]){stack.push(i%nums.length);}else{while(!stack.isEmpty() && nums[i%nums.length]>nums[stack.peek()]){res[stack.peek()]=nums[i%nums.length];stack.pop();}stack.push(i%nums.length);}}return res;}
}

时间复杂度：O（n）
空间复杂度：O（n）

42. 接雨水

在这里插入图片描述

思路： 维护一个单调栈，当到的位置i小于或等于栈顶元素，直接入栈。
如果是大于栈顶的元素。循环以下操作：
需要取出栈顶位置的height作为凹槽的最低端，获取前一个栈顶元素（但不pop！），比较前一个栈顶元素的height和height[i]，用更小的那个减去凹槽最底端，作为h。
i-前一个栈顶元素的下标-1作为w。
计算h*w，累加到res中。

class Solution {public int trap(int[] height) {Deque<Integer> stack=new LinkedList<>();stack.push(0);int sum=0;for(int i=1;i<height.length;i++){if(!stack.isEmpty() && height[i]<=height[stack.peek()]){stack.push(i);}else{while(!stack.isEmpty() && height[i]>=height[stack.peek()]){int mid=stack.pop();//凹槽底部的坐标if(stack.isEmpty()) break;int pre=stack.peek();//前一个比mid位置高的位置int w=i-pre-1;int h=Math.min(height[i],height[pre])-height[mid];sum+=w*h;}stack.push(i);} }return sum;}
}