第十章单调栈 part02 503.下一个更大元素II 42. 接雨水

第六十二天| 第十章单调栈 part02 503.下一个更大元素II 42. 接雨水

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

题目链接：https://leetcode.cn/problems/next-greater-element-ii/
题目介绍：
- 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
  
  数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
  
  示例 1:
```
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
```
思路：
- 本题与“每日最高温度”的区别在于：
  - 本题改成**循环数组**了
    - 成环之后怎么操作呢？这里提供一种思路，凡是成环的题目都可以这么求解
    - 首先遍历的下标最大值为数组长度的2倍，我们要操作的下标的i对数组长度取模
    - 即：
      - for (int i = 1; i < nums.length * 2; i++) {// nums[i % nums.length] }
- 其他代码一样
代码：

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

二、42. 接雨水

题目链接：https://leetcode.cn/problems/trapping-rain-water/

题目介绍：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

思路：
- 本题一个最关键的思路是：
  - 定位当前元素左边第一个最大的值和右边第一个最大的值，高度就是min(左边第一个最大的值，右边第一个最大的值)，宽度就是右边的下标-左边的下标-1，当前元素对应的雨水，就是高度乘以宽度得到的面积，最后再求和。
  - 单调栈还是单调递增的
    - 右边第一个最大的值，是当前元素大于栈口元素时，当前元素就是栈口元素的右边第一个最大的的值
    - 左边第一个最大的值，是栈口元素在栈中的下一个值
代码：

class Solution {public int trap(int[] height) {// 用于接收结果int sum = 0;Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < height.length; i++) {if (height[i] <= height[stack.peek()]) {stack.push(i);} else {while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int mid = stack.pop();// 因为下面有对栈操作，所以需要判断栈不为空if (!stack.isEmpty()) {int left = stack.peek();int h = Math.min(height[left], height[i]) - height[mid];int w = i - stack.peek() - 1;sum += h * w;}}stack.push(i);}}return sum;}
}