代码随想录第五十九天

Leetcode 503. 下一个更大元素 II

题目链接: 下一个更大元素 II
自己的思路:没想到哈哈哈哈！！

正确思路:这个题在单调栈的情况下转了一个弯，就是需要取一个模操作，用来模拟一个数组的循环过程！！！！

代码:

class Solution {public int[] nextGreaterElements(int[] nums) {int length = nums.length;LinkedList<Integer> st = new LinkedList<>();st.addFirst(0);int[] res = new int[length];Arrays.fill(res,-1);for (int i =1;i<2*length;i++){//单调栈逻辑if(nums[i%length]<=nums[st.getFirst()%length]) st.addFirst(i);else{while(!st.isEmpty()&&nums[i%length]>nums[st.getFirst()%length]){res[st.getFirst()%length] = nums[i%length];st.removeFirst();}st.addFirst(i);}}return res;}
}

Leetcode 42. 接雨水

题目链接: 接雨水
自己的思路:想不到！！！！

正确思路:利用单调栈来存储之前遍历的值，这个题应该是找左边第一个比当前元素大的，右边第一个比当前元素大的，两者进行比较，找最小值，求得的最小值减中间元素的高度就是雨水的高，然后我们利用单调栈存储的下标来找雨水的宽就可以，求得宽以后，两个相乘就可以得到雨水面积！！！！！

代码:

class Solution {public int trap(int[] height) {int length = height.length;int res = 0;LinkedList<Integer> st = new LinkedList<>();st.addFirst(0);for (int i =0;i<length;i++){if (height[i]<=height[st.getFirst()]) st.addFirst(i);else{while(!st.isEmpty()&&height[i]>height[st.getFirst()]){int temp = st.removeFirst();if (!st.isEmpty()) {//雨水高度int h = Math.min(height[i],height[st.getFirst()])-height[temp];//中间部分的宽度int w = i-st.getFirst()-1;//可能有0的面积，不需要加if (h*w>0) res += h*w;}}st.addFirst(i);}}return res;}
}