【科学刷题】接雨水：从1维到2维

本文主要是介绍【科学刷题】接雨水：从1维到2维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

1 【1维】接雨水
- 1.1 DP 解法
- 1.2 单调栈解法
- 1.3 堆解法
2【1维】盛最多水的容器
3【2维】接雨水

1 【1维】接雨水

42. 接雨水

1.1 DP 解法

时间复杂度： $O (N)$

Python

class Solution:def trap(self, height: List[int]) -> int:sum = 0n = len(height)max_left = [0] * nmax_right = [0] * nfor i in range(1, n - 1):max_left[i] = max(max_left[i - 1], height[i - 1])for i in reversed(range(1, n - 1)):  # range(n - 2, 0, -1):max_right[i] = max(max_right[i + 1], height[i + 1])for i in range(1, n - 1):min_height = min(max_left[i], max_right[i])sum += max(0, min_height - height[i])return sum

class Solution {
public:int trap(vector<int>& height) {int n=height.size();vector<int> left(n,0);vector<int> right(n,0);int ans=0;for(int i=1;i<n;++i){left[i]=max(left[i-1],height[i-1]);}for(int i=n-2;i>=0;--i){right[i]=max(right[i+1],height[i+1]);}for(int i=1;i<n-1;++i){ans+=max(0,min(left[i],right[i])-height[i]);}return ans;}
};

1.2 单调栈解法

时间复杂度： $O (N)$

class Solution:def trap(self, height: List[int]) -> int:n = len(height)stack = []ans = 0#         □# □       □# □ □   □ □# 2 1 0 1 3#       ↑ ↑ 触发出栈情况# h:    1 1# l:    1 3# 出站后的pre变量代表了前一个高度for i in range(n):while stack and height[stack[-1]] < height[i]:pre = stack.pop()# 如果stack为空，表示 [2, 3, 4] 这种情况，围不起来if not stack:breakt = stack[-1]h = min(height[t], height[i]) - height[pre]  # 当前高度 - 上一个高度l = i - t - 1ans += h * lstack.append(i)return ans

1.3 堆解法

时间复杂度： $O(N\log N)$

class Solution:def trap(self, height: List[int]) -> int:if not height:return 0n = len(height)vis = [0] * npq = []for i in (0, n - 1):vis[i] = Trueheapq.heappush(pq, (height[i], i))ans = 0while pq:wh, x = heapq.heappop(pq)for dx in [-1, 1]:cx = x + dxif not (0 <= cx < n):continueif vis[cx]:continuech = height[cx]ans += max(0, wh - ch)vis[cx] = Trueheapq.heappush(pq, (max(ch, wh), cx))return ans

2【1维】盛最多水的容器

11. 盛最多水的容器

双指针：

class Solution:def maxArea(self, height: List[int]) -> int:l = 0n = len(height)r = n - 1ans = 0while l < r:ans = max((r - l) * min(height[l], height[r]), ans)if height[l] < height[r]:l += 1else:r -= 1return ans

3【2维】接雨水

407. 接雨水 II

时间复杂度： $O(NM\log (N+M))$

class Solution:def trapRainWater(self, heightMap: List[List[int]]) -> int:m, n = len(heightMap), len(heightMap[0])pq = []vis = [[0] * n for _ in range(m)]for i in range(m):for j in range(n):if i in (0, m - 1) or j in (0, n - 1):heapq.heappush(pq, (heightMap[i][j], i, j))vis[i][j] = 1dirs = [-1, 0, 1, 0, -1]ans = 0while pq:wh, x, y = heapq.heappop(pq)for k in range(4):nx, ny = x + dirs[k], y + dirs[k + 1]if 0 <= nx < m and 0 <= ny < n and vis[nx][ny] == 0:ch = heightMap[nx][ny]ans += max(0, wh - ch)vis[nx][ny] = 1heapq.heappush(pq, (max(wh, ch), nx, ny))return ans