LeetCode-42. 接雨水【栈 数组 双指针 动态规划 单调栈】

题目描述：

给定 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

提示：
n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

解题思路一：单调栈，维护一个单调递减栈。每当遇到当前元素大于栈顶元素就出栈，在出栈时更新答案。当遇到出栈的情况，若单调栈栈左边有一个元素则必有height[left] > height[top]，有因为当前元素大于栈顶，那么可以得到当前的接到的雨水量，宽是i - left - 1，长是min(height[i], height[left]) - height[top]。根据宽度和高度即可计算得到该区域能接的雨水量。

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

        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                top = stack.pop()
                if not stack: break
                left = stack[-1]
                currWeith = i - left - 1
                currHeight = min(height[i], height[left]) - height[top]
                ans += currWeith * currHeight
            stack.append(i)

        return ans

时间复杂度：O(n) 其中 n 是数组 height的长度。从 0 到 n?1 的每个下标最多只会入栈和出栈各一次。
空间复杂度：O(n) 空间复杂度主要取决于栈空间，栈的大小不会超过 n。

解题思路二：动态规划，其实很简单。我们只需要知道一个结论，遇到当前元素i，这个位置接的雨水量是min(leftMax[i], rightMax[i]) - height[i]，即该位置左右两边最大值的小的一个减去当前位置的高度。这样就简单了，我们只需要遍历两遍数组得到左边最大值和右边最大值即可。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        n = len(height)
        leftMax = [height[0]] + [0] * (n - 1)
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax = [0] * (n - 1) + [height[n - 1]]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans

时间复杂度：O(n)，其中 n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次，计算能接的雨水总量还需要遍历一次。

空间复杂度：O(n)，其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax和 rightMax。

解题思路三：双指针，用双指针代替动态规划的两个数组，这里用leftMax ， rightMax维护左右当前最大值，如果左边高度小则，left右移且更新答案；如果右边高度大于等于左边，则right左移且更新答案。

这样是一定能够保证，left += 1的时候一定是左边最大值更小。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        
        return ans

时间复杂度：O(n)
空间复杂度：O(1)