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

503.下一个更大元素II

关键点1：先前的一些准备

单调栈：单调栈的含义->用栈记录已经遍历过的元素，再将0元素压入栈

结果集：与给定数组一样大小，结果集初始化为-1

关键点2：核心部分

for循环遍历给定数组：用精简版本解决，我用分开讨论的版本会覆盖值导致报错（这里还未思考明白）

!st.isEmpty() && nums[i%size] > nums[st.peek()]代表现在nums数组的元素值 > nums[栈顶数字]的元素值，那此刻则找到了大于栈顶数字位置对应数值的元素为 nums[i] ，对应的位置为i,

记录此时的结果res[st.peek()] = nums[i%size];

结果记录后弹出栈内比i小的那个数

当结束while循环或者nums[i%size] <= nums[st.peek()]时，则将此时 nums[i%size]的这个i%size再压入栈中st.push(i%size);

关键点3：结果

返回res就行

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

42. 接雨水  

关键点1：先前的一些准备

最开始，如果给定数组的长度为2，直接结果返回0；

单调栈：单调栈的含义->用栈记录已经遍历过的元素，再将0元素压入栈

结果：sum，初始化为0

关键点2：核心部分

for循环遍历给定数组：有三种情况

情况1：height[i] <  height[st.peek()]代表height[i]小于栈里的值对应数组数值的情况，那此刻将i再压入栈中st.push(i);

情况2：height[i] == height[st.peek()]代表：height[i]等于栈里的值对应数组数值的情况，那此刻将栈内元素弹出，再将i压入栈中 st.pop();  st.push(i);

情况3：!st.isEmpty() && height[i] > height[st.peek()]代表height[i]大于栈里的值对应数组数值的情况，那此刻则找到了大于栈顶数字位置对应数值的元素为 height[i] ，对应的位置为i,

3-1：记录栈里这个值mid = st.peek();

3-2：弹出栈内比i小的那个数，此时栈内剩下的这个数，就是原来mid左边比mid大的那个数

3-3：再判断栈是否为空if(!st.isEmpty())，求解h与w
//h = min(左边的高度,右边的高度)-中间的高度
int h = Math.min(height[st.peek()],height[i])-height[mid];
//w = 右边的横坐标-左边的横坐标-1
int w = i - st.peek() - 1;
sum += h*w;

3-4：当结束while循环，则将此时 height[i]的这个i再压入栈中st.push(i);

关键点3：结果

返回sum就行

class Solution {public int trap(int[] height) {if(height.length ==2){return 0;}Stack<Integer> st = new Stack<>();st.push(0);int sum = 0;for(int i = 1; i < height.length;i++){//height[i]小于栈里的值对应数组数值的情况if(height[i] < height[st.peek()]){st.push(i);//height[i]等于栈里的值对应数组数值的情况}else if(height[i] == height[st.peek()]){st.pop();st.push(i);//height[i]大于栈里的值对应数组数值的情况}else{while(!st.isEmpty() && height[i] > height[st.peek()]){int mid = st.peek();//记录栈里这个值st.pop();//弹出栈里这个值是为了拿到栈里第二个值，也就是mid的左边的高度if(!st.isEmpty()){// h = min(左边的高度,右边的高度)-中间的高度int h = Math.min(height[st.peek()],height[i])-height[mid];// w = 右边的横坐标-左边的横坐标-1int w = i - st.peek() - 1;sum += h*w;}}st.push(i);}}return sum;}
}