● 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;}