代码随想录day62 | 单调栈P2 | ● 503. ● 42.

本文主要是介绍代码随想录day62 | 单调栈P2 | ● 503. ● 42.，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

终于来到了大名鼎鼎的接雨水, 舍友的23年暑期面试就是接雨水 XD

503.下一个更大元素II 

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

思路

关键在于如何实现循环数组

原本的想法是将原本数组 * 2 复制一份连接到原来的数组 然后再将找到的索引resize到原数组大小上, 确实可行 但不如直接在遍历的过程中模拟走了两边nums。

只需要在lc739.每日温度 解法的基础上将 i 替换为 i % nums.length 即可

代码

class Solution {public int[] nextGreaterElements(int[] nums) {int [] res = new int[nums.length];Arrays.fill(res, -1);Deque<Integer> stack = new LinkedList<Integer>();stack.push(0);for(int i = 1; i < 2 * nums.length; 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;}
}

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

输入：height = [4,2,0,3,2,5]
输出：9

class Solution {public int trap(int[] height) {int num = 0;//res记录索引int [] res = new int [height.length];Arrays.fill(res, -1);Deque<Integer> st = new LinkedList<>();st.push(0);for(int i = 1; i<height.length; i++){if(height[i] == height[st.peek()]){st.pop();st.push(i);}elseif(height[i] < height[st.peek()]){st.push(i);}else{while(!st.isEmpty() && height[i] > height[st.peek()]){int mid = st.pop();if (!st.isEmpty()) {num += getWater(height, st.peek(), i, mid);}}st.push(i);}}return num;}public int getWater(int [] height, int start, int end, int mid){int h = Math.min(height[start], height[end]);int num = 0,cur = 0;for(int i = start + 1; i < end ; i++){cur = h - height[mid];num += cur;}return num;}
}

这篇关于代码随想录day62 | 单调栈P2 | ● 503. ● 42.的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！