前言

代码随想录算法训练营day59

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

1.题目

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] )，返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]

提示:

1. 1 <= nums.length <= 104
2. -109 <= nums[i] <= 109

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/next-greater-element-ii

2.解题思路

方法一：单调栈 + 循环数组

思路及算法

我们可以使用单调栈解决本题。单调栈中保存的是下标，从栈底到栈顶的下标在数组 numsnums 中对应的值是单调不升的。

每次我们移动到数组中的一个新的位置 ii，我们就将当前单调栈中所有对应值小于 nums[i]nums[i] 的下标弹出单调栈，这些值的下一个更大元素即为 nums[i]nums[i](证明很简单：如果有更靠前的更大元素，那么这些位置将被提前弹出栈)。随后我们将位置 ii 入栈。

但是注意到只遍历一次序列是不够的，例如序列 [2,3,1][2,3,1]，最后单调栈中将剩余 [3,1][3,1]，其中元素 [1][1] 的下一个更大元素还是不知道的。

一个朴素的思想是，我们可以把这个循环数组「拉直」，即复制该序列的前 n−1n−1 个元素拼接在原序列的后面。这样我们就可以将这个新序列当作普通序列，用上文的方法来处理。

而在本题中，我们不需要显性地将该循环数组「拉直」，而只需要在处理时对下标取模即可。

3.代码实现

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

二、Leetcode 42. 接雨水

1.题目

给定 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 个单位的雨水(蓝色部分表示雨水)。

示例 2：

输入：height = [4,2,0,3,2,5] 输出：9

提示：

1. n == height.length
2. 1 <= n <= 2 * 104
3. 0 <= height[i] <= 105

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/trapping-rain-water

2.解题思路

方法一：动态规划

对于下标 ii，下雨后水能到达的最大高度等于下标 ii 两边的最大高度的最小值，下标 ii 处能接的雨水量等于下标 ii 处的水能到达的最大高度减去 height[i]height[i]。

朴素的做法是对于数组 heightheight 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 heightheight 的长度为 nn，该做法需要对每个下标位置使用 O(n)O(n) 的时间向两边扫描并得到最大高度，因此总时间复杂度是 O(n2)O(n2)。

上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n)O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n)O(n) 的时间内预处理得到每个位置两边的最大高度。

创建两个长度为 nn 的数组 leftMaxleftMax 和 rightMaxrightMax。对于 0≤i

显然，leftMax[0]=height[0]leftMax[0]=height[0]，rightMax[n−1]=height[n−1]rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下：

1. 当 1≤i≤n−11≤i≤n−1 时，leftMax[i]=max⁡(leftMax[i−1],height[i])leftMax[i]=max(leftMax[i−1],height[i])；
2. 
3. 当 0≤i≤n−20≤i≤n−2 时，rightMax[i]=max⁡(rightMax[i+1],height[i])rightMax[i]=max(rightMax[i+1],height[i])。

因此可以正向遍历数组 heightheight 得到数组 leftMaxleftMax 的每个元素值，反向遍历数组 heightheight 得到数组 rightMaxrightMax 的每个元素值。

在得到数组 leftMaxleftMax 和 rightMaxrightMax 的每个元素值之后，对于 0≤i

动态规划做法可以由下图体现。

3.代码实现

```java class Solution { public int trap(int[] height) { int n = height.length; if (n == 0) { return 0; }

1. int[] leftMax = new int[n];
2.     leftMax[0] = height[0];
3. for (int i = 1; i < n; ++i) {
4.         leftMax[i] = Math.max(leftMax[i - 1], height[i]);
5.     }
6. 
7.     int[] rightMax = new int[n];
8.     rightMax[n - 1] = height[n - 1];
9. for (int i = n - 2; i >= 0; --i) {
10.         rightMax[i] = Math.max(rightMax[i + 1], height[i]);
11.     }
12. 
13.     int ans = 0;
14. for (int i = 0; i < n; ++i) {
15.         ans += Math.min(leftMax[i], rightMax[i]) - height[i];
16.     }
17. return ans;
18. }

}

```