42.接雨水

monotonic stack, 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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

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

提示：

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

单调栈其实就是在栈的基础上，维持一个栈内元素单调。

https://github.com/SharingSource/LogicStack-LeetCode
在这道题，由于需要找某个位置两侧比其高的柱子（只有两侧有比当前位置高的柱子，当前位置才能接下雨水），我们可以维持栈内元素的单调递减。
PS.找某侧最近一个比其大的值，使用单调栈维持栈内元素递减；找某侧最近一个比其小的值使用单调栈维持栈内元素递增 ….
当某个位置的元素弹出栈时，例如位置 a ，我们自然可以得到 a 位置两侧比 a 高的柱子：
一个是导致 a位置元素弹出的柱子( a右侧比 a高的柱子)
一个是 a弹栈后的栈顶元素(a 左侧比 a 高的柱子)
当有了 a 左右两侧比 a 高的柱子后，便可计算 a 位置可接下的雨水量。

python

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        water = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                distance = i - stack[-1] - 1
                bounded_height = min(height[i], height[stack[-1]]) - height[top]
                water += distance * bounded_height
            stack.append(i)
        return water

这段代码实现了一个算法，用于计算给定高度数组 height 中可以 trapping 的雨水总量。这个算法使用了栈来高效地解决这个问题。
代码解读
处理栈中的元素
python
        while stack and height[i] > height[stack[-1]]:
当栈不为空且当前高度 height[i] 大于栈顶元素对应的高度 height[stack[-1]] 时，进入循环。
弹出栈顶元素
python
            top = stack.pop()
弹出栈顶元素 top，top 是当前高度较低的柱子的索引。
检查栈是否为空
python
            if not stack:
                break
如果栈为空，说明没有更高的柱子可以形成积水区域，跳出循环。
计算积水区域
python
            distance = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[top]
            water += distance * bounded_height
distance：计算当前柱子 i 和栈顶柱子 stack[-1] 之间的距离，减去 1 是因为不包括两端的柱子。
bounded_height：计算当前柱子 i 和栈顶柱子 stack[-1] 之间的最小高度，减去弹出的柱子 top 的高度，得到积水的高度。
water += distance * bounded_height：计算当前积水区域的水量，并累加到 water 中。

双指针

python

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = left = pre_max = suf_max = 0
        right = len(height) - 1
        while left < right:
            pre_max = max(pre_max, height[left])
            suf_max = max(suf_max, height[right])
            if pre_max < suf_max:
                ans += pre_max - height[left]
                left += 1
            else:
                ans += suf_max - height[right]
                right -= 1
        return ans

单调栈相当于按行接雨水，双指针相当于按列接雨水？
确实，单调栈和双指针方法在处理“接雨水”问题时采用了不同的思路，但最终都能正确计算出能够接住的雨水总量。下面简要分析这两种方法的工作原理：
单调栈（按行接雨水）
单调栈方法通过维护一个递减栈来找到每个位置左侧和右侧的第一个更高柱子，进而计算该位置上方能接住的雨水量。这种方法可以看作是逐行计算雨水量，因为每次从栈中弹出一个元素时，实际上是在计算该元素上方的水平层（即一行）的雨水量。具体来说，当遇到一个比栈顶元素高的柱子时，就找到了一个可以蓄水的区域，然后根据左右边界的高度差和距离计算出该行的雨水量。
双指针（按列接雨水）
双指针方法则是通过两个指针从数组的两端向中间移动，同时记录左右两边的最大高度。在每一步中，选择较短的一边进行处理，因为水位总是由较短的一边决定的。如果左边高度小于右边高度，那么左边当前柱子上方能接住的雨水量就是左边最大高度减去当前高度；反之亦然。这种方法可以看作是逐列计算雨水量，因为每次移动指针时，实际上是在计算当前指针所指向柱子上方的雨水量。
比较
单调栈 更适合理解为按照行来计算雨水量，因为它关注的是每个局部凹陷处（即两根较高柱子之间的一根或几根较低柱子）的雨水量，这些凹陷处可以想象成一个个水平的水层。
双指针 则更适合理解为按照列来计算雨水量，因为它直接计算每个柱子上方能接住的雨水量，而不需要显式地找出每个凹陷处。
两种方法虽然计算方式不同，但是都能有效地解决问题，并且时间复杂度都是 O(n)，其中 n 是高度数组的长度。空间复杂度方面，单调栈方法需要额外的空间来存储栈，而双指针方法只需要常数级别的额外空间。

42.接雨水 ​

42.接雨水