[leetcode/lintcode 題解] 阿裡面試真題詳解：接雨水

描述

給出 n 個非負整數，代表一張X軸上每個區域寬度為 1 的海拔圖, 計算這個海拔圖最多能接住多少（面積）雨水。

線上評測位址：

領扣題庫官網

樣例1
輸入: [0,1,0]
輸出: 0           

樣例2
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6           

解法思路

• 使用九章算法班中講過的相向型雙指針算法。 整個算法的思想是計算每個位置上可以盛放的水，累加起來。
• 記錄如下幾個值：
• left, right => 左右指針的位置
• left_max, right_max => 從左到右和從右到左到 left, right 為止，找到的最大的 height
• 每次比較 left_max 和 right_max，如果 left_max 比較小，就挪動 left 到 left + 1。 與此同時，檢視 left 這個位置上能夠盛放多少水，這裡有兩種情況：
• 一種是 left_max > heightsleft，這種情況下，水可以盛放 left_max - heightsleft 那麼多。因為右邊有 right_max 擋着，左側可以到 left_max。
• 一種是 left_max <= heightsleft，這種情況下，水無法盛放，會從左側流走，此時更新 left_max 為 heightsleft
• left_max >= right_max 的情況類似處理。

算法複雜度

• 時間複雜度：O(n)O(n)，空間複雜度 O(1)

  class Solution:
  """
  @param heights: a list of integers
  @return: a integer
  """
  def trapRainWater(self, heights):
      if not heights:
          return 0
  
      left, right = 0, len(heights) - 1
      left_max, right_max = heights[left], heights[right]
      water = 0
      while left <= right:
          if left_max < right_max:
              left_max = max(left_max, heights[left])
              water += left_max - heights[left]
              left += 1
          else:
              right_max = max(right_max, heights[right])
              water += right_max - heights[right]
              right -= 1
  
      return water           

  更多題解參考： 九章官網solution