各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 68 天。今天力扣上的每日一题是「面试题 17.21. 直方图的水量」。

解题思路

我使用的是 面向列的计算

面向列的计算比面向行的计算更容易，我们只用考虑当前的位置的左右最高木板的高度。

1. 暴力解法

每个位置能接多少雨水，很容易想到「木桶效应」，即是由两边最短的木板限制的。那么直观思路就是，对于每个位置，向左右找最高的木板；当前位置能放的水量是：左右两边最高木板的最低高度 - 当前高度。

这个做法应该是本题的最简单的做法。

下图的红色柱子表示当前要求的位置，两个黄色柱子分别表示左右最高的柱子。
image.png

代码也非常简单：

  1. class Solution(object):
  2.     def trap(self, height):
  3.         res = 0
  4.         # 第 0 个位置和 最后一个位置不能蓄水，所以不用计算
  5.         for i in range(1, len(height) - 1):
  6.             # 求右边的最高柱子
  7.             rHeight = max(height[i + 1:])
  8.             # 求左边的最高柱子
  9.             lHeight = max(height[:i])
  10.             # 左右两边最高柱子的最小值 - 当前柱子的高度
  11.             h = min(rHeight, lHeight) - height[i]
  12.             # 如果能蓄水
  13.             if h > 0:
  14.                 res += h
  15.         return res
  • 时间复杂度：$O(N^2)$
  • 空间复杂度：$O(1)$

2. 动态规划

从上面的代码思路中我们看到，对于每个位置，我们都暴力向两边求最高木板，这里其实是有重复计算的。比较直观的优化思路是：先提前遍历一次，求出每个位置左右最高的模板，把结果保存到数组里。就可以避免在求解接雨水的 for 循环中计算高度了。

  1. class Solution(object):
  2.     def trap(self, height):
  3.         N = len(height)
  4.         # 如果小于等于两个柱子，是无法蓄水的
  5.         if N <= 2: return 0
  6.         # 求每个位置左边的最高柱子
  7.         lHeight = [0] * N
  8.         # lHeight 第 0 个位置初始化为 height[0]
  9.         lHeight[0] = height[0]
  10.         # 求每个位置右边的最高柱子
  11.         rHeight = [0] * N
  12.         # rHeight 最后一个位置初始化为 height[N - 1]
  13.         rHeight[N - 1] = height[N - 1]
  14.         # 求每个位置左边最高柱子高度
  15.         for i in range(1, N):
  16.             lHeight[i] = max(lHeight[i - 1], height[i])
  17.         # 求每个位置右边最高柱子高度
  18.         for i in range(N - 2, -1, -1):
  19.             rHeight[i] = max(rHeight[i + 1], height[i])
  20.         res = 0
  21.         # 这个思路和上面的暴力解法一样的
  22.         for i in range(1, len(height) - 1):
  23.             h = min(rHeight[i], lHeight[i]) - height[i]
  24.             if h > 0:
  25.                 res += h
  26.         return res
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

3. 双指针

双指针解法是上面的解法的进一步优化，主要作用是为了降低空间复杂度。

使用了两个指针 left 和 right 分别指向左右两个端点的柱子。
另外用 lHeight 和 rHeight 分别表示左右两个指针遇到过的最高的柱子，注意上面的动态规划做法是提前算出来每个位置左右的最高柱子，而双指针解法是在遍历的过程中统计遇到过的最高柱子。

双指针移动的思想是看哪 left 和 right 两个柱子哪个更矮，因为蓄水时的瓶颈是更矮的柱子，而更高的柱子其实是不用考虑的。所以每次把更矮的那个柱子向中间移动。

详细解释可以看 力扣加加 。

  1. class Solution(object):
  2.     def trap(self, height):
  3.         N = len(height)
  4.         if N < 2: return 0
  5.         left, right = 0, N - 1
  6.         lHeight = rHeight = 0
  7.         res = 0
  8.         while left < right:
  9.             if height[left] < height[right]:
  10.                 if height[left] < lHeight:
  11.                     res += lHeight - height[left]
  12.                 else:
  13.                     lHeight = height[left]
  14.                 left += 1
  15.             else:
  16.                 if height[right] < rHeight:
  17.                     res += rHeight - height[right]
  18.                 else:
  19.                     rHeight = height[right]
  20.                 right -= 1
  21.         return res
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

    刷题心得

最近工作非常忙，题解质量降低了，很抱歉。

参考资料：

力扣官方题解
代码随想录
力扣加加

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！