力扣热题100刷题-twoPointers-42-接雨水

less than 1 minute read

42. 接雨水

给定一个非负整数数组 height ，每个整数代表一个柱子的高度，柱子的宽度为 1。计算下雨后，这些柱子能接多少雨水。

这道题是求解一个二维图形中可以容纳多少“水”，核心在于确定每个位置上方能蓄水的高度。

最直观的想法是，对于数组中的每一个位置 i，它能接的雨水数量取决于其左侧最高柱子和右侧最高柱子中最矮的那个。具体来说，i 位置的水位高度是 min(左侧最高柱子高度, 右侧最高柱子高度)。那么，i 位置能接的雨水量就是 水位高度 - height[i]。

但是，每次都去遍历查找左右两侧的最高柱子，时间复杂度会达到 O(n^2)，效率不高。

我们可以优化这个过程。通过两次遍历，预先计算出每个位置的左侧最高和右侧最高。

这个方法将时间复杂度降到了 O(n)，但需要 O(n) 的额外空间。这对应了代码中的 trapByArray 方法。

在思路一的基础上，我们思考是否可以优化空间复杂度，去掉额外的 preMax 和 sufMax 数组。

我们可以使用两个指针，left 从数组开头，right 从数组末尾，相向移动。同时维护两个变量，preMax 表示 [0...left] 区间的最高柱子，sufMax 表示 [right...n-1] 区间的最高柱子。

在 left 和 right 指针相遇之前，循环执行以下逻辑：

比较 preMax 和 sufMax。
如果 preMax < sufMax：
- 这意味着，对于 left 指针所在的位置，它的左侧最高墙（preMax）比右侧已经看到的最高墙（sufMax）要矮。由于 sufMax 只是 [right...n-1] 的最大值，整个数组 [left...n-1] 的真实最大值肯定不小于 sufMax。因此，left 位置的水位就由 preMax 决定了。
- 计算 left 位置的雨水量：preMax - height[left]，累加到总结果中。
- left 指针右移，并更新 preMax。
如果 preMax >= sufMax：
- 同理，对于 right 指针所在的位置，它的右侧最高墙（sufMax）是瓶颈。right 位置的水位由 sufMax 决定。
- 计算 right 位置的雨水量：sufMax - height[right]，累加到总结果中。
- right 指针左移，并更新 sufMax。

这个方法非常巧妙，它在一次遍历中完成了计算，时间复杂度为 O(n)，空间复杂度为 O(1)。这对应了代码中的 trapByTwoPointers 方法。

这道题也可以用单调栈来解决。栈里存放的是柱子的索引。我们维护一个单调递减栈。

当遍历到的当前柱子高度 height[i] 小于等于栈顶柱子高度时，将 i 入栈。
当 height[i] 大于栈顶柱子高度时，说明出现了一个“凹”槽，可以蓄水。此时，栈顶元素 top 就是凹槽的底部。top 出栈后，新的栈顶元素 left = st.peek() 就是凹槽的左边界，而当前柱子 i 就是右边界。
水的宽度是 i - left - 1，高度是 min(height[left], height[i]) - height[top]。
如此循环，直到栈为空或当前柱子不再高于栈顶。

单调栈提供了一个不同的视角，对于求解“最近的最大/最小值”这类问题非常有效。

这道题的几种解法都非常经典，体现了算法优化的常见思路。

动态规划/空间换时间：预计算并存储重复计算的结果。这个思想在很多问题中都有应用，比如斐波那契数列、最长公共子序列等。
双指针：特别是相向双指针，常用于有序数组或需要从两端同时处理的问题。它能有效地将 O(n^2) 的暴力搜索优化到 O(n)。
- 11. 盛最多水的容器：同样是双指针从两端向中间收敛，每次移动较短的那一边的指针。
- 15. 三数之和：在排序后，固定一个数，然后用双指针在剩余部分查找另外两个数。
单调栈：适用于解决“下一个更大元素”、“上一个更小元素”等问题。
- 84. 柱状图中最大的矩形：一个经典的单调栈应用，和本题的单调栈解法有相似之处。
- 739. 每日温度：用单调栈寻找下一个比当天温度高的日子。

通过本题，可以深刻理解以上几种数据结构和算法思想的巧妙之处，并学会在不同场景下选择合适的方案来优化时间和空间复杂度。