代码随想录打卡第62天|● 503.下一个更大元素II ● 42. 接雨水

● 503.下一个更大元素II

题目：给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
在这里插入图片描述

题目链接：503.下一个更大元素II
解题思路：重点在于循环只需将循环变为线性即可，double数组模拟循环的状况
代码如下：

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

● 42. 接雨水（重点）

题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
在这里插入图片描述

题目链接： 42. 接雨水
解法一：双指针法
解题思路：维护当前列左边和右边的最高列
使用数组维护
获取左边最高列的值
从左往右遍历如果当前位置高度大于其前一位最高列的值，它的最高列为本身。否则为前一列最高值
获取右边最高列的值
与获取左边的逻辑同理，但是从右往左遍历
计算体积：Math.min(maxleft[i],maxright[i])-height[i] 宽度为1
代码如下：

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

解法二：单调栈法
情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
入栈
情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
入栈
情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]
当前元素为右柱子栈顶元素为中间栈中第二个元素为左柱子
结束计算后将栈顶元素弹出
代码如下：

 public int trap(int[] height) {
        Stack<Integer> stack=new Stack<>();
        int res=0;
        stack.push(0);
        for(int i=1;i<height.length;i++){
            while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
                int midden=stack.pop();
                if(!stack.isEmpty()){
                    int left=stack.peek();
                    res+=(Math.min(height[i],height[left])-height[midden])*(i-left-1);
                }
            }
            stack.push(i);
        }
        return res;
    }