Day 19 拓展:42|407. 接雨水I II, 11. 盛最多水容器

42. 接雨水

  • 思路
    • example
    • 木桶效应,短板效应
    • 每个格子左右两边最大值的短板(h), h - height[i] if this is \geq 0
    • 解法1:暴力
      • 复杂度. 时间:O(n^2), 空间: O(1)
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        res = 0
        for i in range(n):
            leftMax = 0
            for j in range(0, i):
                leftMax = max(leftMax, height[j])
            rightMax = 0
            for j in range(i+1, n):
                rightMax = max(rightMax, height[j])
            if min(leftMax, rightMax) > height[i]:
                res += min(leftMax, rightMax) - height[i]
        return res
  • 解法2:动规 (DP)
    • 维护leftMax (-->),rightMax数组 (<--)
    • leftMax[i]: max of height[0], ..., height[i-1]
    • rightMax[i]: max of height[i+1], ..., height[n-1]
      • 复杂度. 时间:O(n), 空间: O(n)
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        leftMax = [0] * n
        rightMax = [0] * n
        for i in range(1, n):
            leftMax[i] = max(leftMax[i-1], height[i-1])
        for i in range(n-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], height[i+1])
        res = 0
        for i in range(n):
            h = min(leftMax[i], rightMax[i])
            if h > height[i]:
                res += h - height[i]
        return res
  • 解法3:双指针: left, right. -->*<--
    • 指针移动规则?
      • 给定left, right (left <= right), 希望能够确定left 和 right其中一个位置的水位 (所能容纳的水量)。
      • 可得到left之前(不包括left) 最大高度,以及right之后最大高度
        • 假设height[left-1] < height[right+1], 则left这个位置的水位必然由leftMax[left]决定 (这个位置的储水不可能从右边界流出去), 从而可以确定left这个位置的水位:max(0, leftMax[left] - height[left])
          • 下一步:left += 1
        • 假设height[left -1] >= height[right+1], ...., 可以由rightMax[right]确定right这个位置的水位
          • 下一步:right -= 1
    • 上面的过程可以只维护当前的leftMax和rightMax 这两个数值。
    • 复杂度. 时间:O(n), 空间: O(1)
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 2:
            return 0
        left, right = 1, n-2 
        leftMax, rightMax = height[0], height[n-1]
        res = 0
        while left <= right:
            if height[left-1] < height[right+1]:
                leftMax = max(leftMax, height[left-1])
                res += max(0, leftMax - height[left])
                left += 1
            else:
                rightMax = max(rightMax, height[right+1])
                res += max(0, rightMax - height[right])
                right -= 1
        return res
  • 解法四:优先队列 heapq (size = 2)
    • que: 最小堆, 初始化存储第一个和最后一个 (高度,index)
    • 从外往内遍历“填充”水位(因为水一定是从左右两个边界溢出),得用que,每次pop que 首位(heapq.heappop(que)) (左右边界中的最小高度---短板效应),然后判断该高度对应Index的邻居的水位。更新res, 更新新的边界入最小堆。
    • 可以维护一个visited数组,确保不会重复访问。
    • 复杂度. 时间:O(n), 空间: O(1)
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 2:
            return 0
        que = []
        heapq.heappush(que, (height[0], 0))
        heapq.heappush(que, (height[n-1], n-1))
        visited = [False] * n
        visited[0] = visited[n-1] = True
        direction = [-1, 1]
        res = 0
        while que:
            min_height, min_index = heapq.heappop(que)
            for i in direction:
                index = min_index + i 
                if index >= 0 and index <= n-1 and visited[index] == False:
                    min_height_new = max(min_height, height[index])
                    res += min_height_new - height[index]
                    visited[index] = True
                    heapq.heappush(que, (min_height_new, index))
        return res

407. 接雨水 II

  • 思路
    • example
    • 接雨水 高维版本
    • 由外身内遍历边界 (水一定是从外边界溢出)
      • 优先队列 (最小堆 heapq)
      • directions方向向量: 方便考察最小边界周围点的水位
      • visited数组避免重复访问
        • 判断visited[x][y]时先检查x,y是否越界。
    • 复杂度. 时间:O(mn), 空间: O(m+n)
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        if m <= 2 or n <= 2:
            return 0
        res = 0
        que = []
        visited = [[False]*n for _ in range(m)]
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        for j in range(n):
            heapq.heappush(que, (heightMap[0][j], (0,j)))
            visited[0][j] = True
            if m - 1 > 0:
                heapq.heappush(que, (heightMap[m-1][j], (m-1,j)))
                visited[m-1][j] = True
        for i in range(1, m-1):
            heapq.heappush(que, (heightMap[i][0], (i,0)))
            visited[i][0] = True
            if n -1 > 0:
                heapq.heappush(que, (heightMap[i][n-1], (i,n-1)))
                visited[i][n-1] = True
        while que:
            min_height, coordinate = heapq.heappop(que)
            x0, y0 = coordinate[0], coordinate[1]
            for direction in directions:
                dx, dy = direction[0], direction[1]
                x, y = x0 + dx, y0 + dy
                if 0<=x<m and 0<=y<n and visited[x][y] == False:
                    min_height_new = max(min_height, heightMap[x][y])
                    res += min_height_new - heightMap[x][y]
                    visited[x][y] = True 
                    heapq.heappush(que, (min_height_new, (x,y)))
        return res 

11. 盛最多水的容器

  • 思路
    • example
    • 短板效应
      • [left, right]: 储水量 = min(height[left], height[right]) * (right - left)
    • 解法1:暴办法
      • 复杂度. 时间:O(n^2), 空间: O(1)
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        res = 0
        for left in range(n):
            for right in range(left+1, n):
                res = max(res, min(height[left], height[right]) * (right - left))
        return res
  • 解法2:双指针, -->*<--
    • left, right = 0, n-1
    • 在更新完[left, right]结果后,考虑left += 1, 或者right -= 1
    • 如果height[left] < height[right]: 考虑left += 1, 这样在宽度减小的情况下,min_height有可能增大;否则如果right-=1, min_height <= height[left],不可能改进结果。
    • 复杂度. 时间:O(n), 空间: O(1)
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left, right = 0, n-1
        res = 0
        while left < right:
            res = max(res, min(height[left], height[right])*(right-left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return res
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容