代码随想录算法训练营Day59 | 503. 下一个更大元素II | 42. 接雨水

503. 下一个更大元素II

题目链接 | 解题思路

本题和每日温度非常相似，只是需要循环数组。最简单的方法当然是直接拼接数组，然后直接使用单调栈，最后修改输出的形状即可。不过这个方法需要修改数组，有额外的空间、时间复杂度。

以下可以直接模拟走两遍数组的过程，而不需要额外的复杂度。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        result = [-1] * len(nums)
        stack = [0]

        for i in range(1, len(nums) * 2):
            if nums[i % len(nums)] <= nums[stack[-1]]:
                stack.append(i % len(nums))
            else:
                while (len(stack) > 0 and nums[i % len(nums)] > nums[stack[-1]]):
                    result[stack[-1]] = nums[i % len(nums)]
                    stack.pop()
                stack.append(i % len(nums))
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14

42. 接雨水

题目链接 | 解题思路

本题真的很经典、很常考！不同解法考验了不同方面的知识，真乃神题！

在开始选择解法之前，一定要先理清思路：究竟是按行还是按列来进行计算？

暴力解法

暴力解法实际上也是双指针。按照列来计算比较容易，此时只需要计算每一列中能够储存的雨水高度即可。每一列的雨水高度取决于

• 这一列左边最高的柱子高度
• 这一列右边最高的柱子高度

（补一张图！）

得到两者中更小的高度后，减去当前列的柱子高度就是雨水高度.
想清楚思路后很容易写出代码，要注意的是最左侧和最右侧的柱子是没办法接雨水的。

class Solution:
    def trap(self, height: List[int]) -> int:
        sum = 0
        for i in range(1, len(height) - 1):
            left_max_height = right_max_height = height[i]
            for left in range(i-1, -1, -1):
                if height[left] > left_max_height:
                    left_max_height = height[left]
            for right in range(i+1, len(height)):
                if height[right] > right_max_height:
                    right_max_height = height[right]
            sum += min(left_max_height, right_max_height) - height[i]
        return sum
1
2
3
4
5
6
7
8
9
10
11
12
13

意料之中，暴力解法的时间复杂度是 $O(n^2)$，会超时。

双指针优化

暴力解法中有大量的重复计算：在计算每一列作为谷底的时候，都要进行一次遍历来得到左侧的最大高度和右侧的最大高度。

优化：可以通过两个静态的数组来分别记录数组中每个位置的左侧最大高度、右侧最大高度，只要以 $O(n)$ 的时间完成这两个记录，就能优化整体的时间复杂度。
实际的记录过程有点类似于简单的 dp。以左侧最大高度为例，

• 如果当前列的高度小于左侧列的左侧最大高度，则 left_higher[i] = left_higher[i-1]；
• 否则，当前列左侧没有比自己更高的，当前列的左侧最大高度即是自己，left_higher[i] = height[i]，

class Solution:
    def trap(self, height: List[int]) -> int:
        left_higher = [0] * len(height)
        left_higher[0] = height[0]
        for i in range(1, len(height)):
            left_higher[i] = max(left_higher[i-1], height[i])

        right_higher = [0] * len(height)
        right_higher[-1] = height[-1]
        for i in range(len(height) - 2, -1, -1):
            right_higher[i] = max(right_higher[i+1], height[i])
        
        sum = 0
        for i in range(1, len(height) - 1):
            sum += min(left_higher[i], right_higher[i]) - height[i]

        return sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

空间换时间的优化，此时的时间复杂度是 $O(n)$，但是空间复杂度也是 $O(n)$，因为记录了两个数组。

单调栈

单调栈在本题中的应用思路有些模糊。一方面，单调栈适用于寻找当前元素左侧/右侧的第一个更大元素值，和本题的“寻找谷地”有紧密的联系；另一方面，之前在思路中提到的是寻找“左侧/右侧的最大高度”，而不是第一个更大元素，这似乎又没有很紧密的关系。

思路转换的突破口在于，要使用单调栈解题，应该按行计算。

1. 按照行计算，就需要找到这一行（一个谷内的行，不是传统意义上的一行）的起始位置。而起始位置就是由这一行的左、右侧第一个更大值的位置决定的。
   

2. 单调栈内的元素顺序、如何取值

   • 栈内的顺序应该是 top-bottom 递增，这样向右搜索的时候，如果当前元素值大于栈口元素值，能够找到栈口元素的右侧第一个更大值，也就知道当前行（栈口元素代表的那一行）的右边界
   • 栈口元素的内部第一个元素值是栈口元素左侧的第一个更大值，也就是当前行的左边界
     

3. 当前元素与栈口元素相等：这个情况不像之前的题目一样直接，需要进行额外的讨论

   • 当遇到高度和栈口元素相等的柱子时，最好将栈口元素（i.e. 下标）弹出，然后压入当前元素（i.e. 下标）。这是因为求当前行的宽度时，需要用最右侧的柱子下标进行计算。
     

   • 当然，注意到上面的用词是“最好”。如果不进行弹出，而是只将当前元素压入，不会影响最后的结果，但是后续会额外做一些雨水量为 0 的计算。

4. 栈内记录的元素：通过单调栈的更新结果来计算雨水量，需要当前行的高和宽。其中高需要列的值，宽需要列的下标，既然通过下标可以直接获取值，栈内只需要记录下标即可。

单调栈的处理逻辑

单调栈的三种情况：

1. 当前的列高度小于栈口元素的高度 height[i] < height[stack[-1]]
   • 将当前的元素压入栈中，更新当前行的位置，同时还没有找到谷的右边界
2. 当前的列高度等于栈口元素的高度 height[i] == height[stack[-1]]
   • optional：将当前栈口元素弹出
   • 仍然在搜索当前行，需要更新当前行的最右侧，保持当前行的高度
3. 当前的列高度大于栈口元素的高度 height[i] > height[stack[-1]]
   • 当前元素即为谷的右边界
   • 将栈口元素弹出作为谷底，此时新的栈口元素可以视作是谷的左边界
   • 得到了谷的左右边界，以及谷底高度，就可以轻松计算出这个谷的接雨水量（注意这是一个横向的计算！）
     • 如果在处理 height[i] == height[stack[-1]] 时没有弹出之前的栈口元素，那么可能会遇到谷内能够接到的雨水量为 0 的情况

class Solution:
    def trap(self, height: List[int]) -> int:
        sum = 0
        stack = [0]

        for i in range(1, len(height)):
            if height[i] < height[stack[-1]]:
                stack.append(i)
            elif height[i] == height[stack[-1]]:
                stack.pop()         # optional, improve performances
                stack.append(i)
            else:
                while (len(stack) > 0 and height[i] > height[stack[-1]]):
                    valley_bottom = stack.pop()     # store it as it is popped
                    if len(stack) > 0:      # possibly empty now
                        curr_height = min(height[stack[-1]], height[i]) - height[valley_bottom]  
                        curr_width = i - stack[-1] - 1
                        sum += curr_height * curr_width
                stack.append(i)
        return sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

单调栈的解法应该是最优的，时间复杂度是 $O(n)$，空间复杂度也是 $O(n)$，并且比双指针 + dp 少记录了一个数组。