代码随想录训练营二刷第六十一天

训练营二刷第六十一天"/>

代码随想录训练营二刷第六十一天

代码随想录训练营二刷第六十一天 | 503.下一个更大元素II ● 42. 接雨水

一、503.下一个更大元素II

题目链接：/
思路：循环数组多遍历一次，逻辑上拼一块往单调栈里放。

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

二、42. 接雨水

题目链接：/
思路：接雨水得是凹槽处才能接，如2,1,3。1是凹槽，h是左右第一个高点中的最小者，w是右侧-左侧-1。如此栈内应放索引，应为自栈顶到栈底单调递减，当前元素小于栈顶加入，等于栈顶替换掉，大于栈顶就找到右边第一个最大值了。此时便可出栈计算。

class Solution {public int trap(int[] height) {Deque<Integer> stack = new LinkedList<>();int sum = 0;stack.push(0);for (int i = 1; i < height.length; i++) {if (height[i] < height[stack.peek()]) {stack.push(i);} else if (height[i] == height[stack.peek()]) {stack.pop();stack.push(i);} else {while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int mid = stack.pop();if (!stack.isEmpty()) {int h = Math.min(height[i], height[stack.peek()]) - height[mid];int w = i - stack.peek() - 1;sum += h * w;}}stack.push(i);}}return sum;}
}