代码随想录算法训练营Day61

算法训练营Day61"/>

代码随想录算法训练营Day61

代码随想录算法训练营Day61|单调栈02

文章目录

• 代码随想录算法训练营Day61|单调栈02
• 一、 503.下一个更大元素II
• 二、42. 接雨水

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

class Solution {public int[] nextGreaterElements(int[] nums) {if(nums == null || nums.length <= 1) {return new int[]{-1};}int size = nums.length;int[] result = new int[size];//存放结果Arrays.fill(result,-1);//默认全部初始化为-1Stack<Integer> st= new Stack<>();for(int i = 0; i < 2*size; i++) {while(!st.empty() && nums[i % size] > nums[st.peek()]) {result[st.peek()] = nums[i % size];st.pop();}st.push(i % size);}return result;}
}

二、42. 接雨水

class Solution {public int trap(int[] height) {int length = height.length;if (length <= 2) return 0;int[] maxLeft = new int[length];int[] maxRight = new int[length];maxLeft[0] = height[0];for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);maxRight[length - 1] = height[length - 1];for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);int sum = 0;for (int i = 0; i < length; i++) {int count = Math.min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}
}