如何高效解决接雨水问题
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 11. Container With Most Water | 🟠 |
| 42. Trapping Rain Water | 🔴 |
Prerequisites
Before reading this article, you should first learn:
LeetCode problem #42 "Trapping Rain Water" is quite interesting and frequently appears in interviews. This article will walk you through step-by-step optimizations to solve this problem.
First, let's look at the problem:
42. Trapping Rain Water | 力扣 | LeetCode |
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5] Output: 9
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
The problem involves using an array to represent a bar chart and asks how much water this bar chart can trap at most.
int trap(int[] height);int trap(vector<int>& height);def trap(height: List[int]) -> int:func trap(height []int) int {} var trap = function(height) {}Let's dive into the solution step by step, from brute force -> memoization -> two-pointer approach, to solve this problem in O(N) time and O(1) space.
Core Idea
For this type of problem, instead of thinking about the whole, we should focus on the parts. Just like in previous articles on dynamic programming for string problems, we don't consider how to handle the entire string, but rather how to handle each character.
With this mindset, the approach to this problem becomes quite simple. Specifically, for a position i, how much water can it hold?
It can hold 2 units of water because the height at height[i] is 0, and the maximum it can hold is 2 units, so 2-0=2.
Why can position i hold up to 2 units of water? Because the water height at position i depends on the tallest bars to its left and right, which we'll call l_max and r_max respectively. The maximum water height at position i is min(l_max, r_max).
Furthermore, the amount of water that position i can hold is:
water[i] = min(
# the highest pillar on the left
max(height[0..i]),
# the highest pillar on the right
max(height[i..end])
) - height[i]
This is the core idea of this problem. We can write a simple brute-force algorithm:
class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
for (int i = 1; i < n - 1; i++) {
int l_max = 0, r_max = 0;
// find the tallest pillar on the right
for (int j = i; j < n; j++)
r_max = Math.max(r_max, height[j]);
// find the tallest pillar on the left
for (int j = i; j >= 0; j--)
l_max = Math.max(l_max, height[j]);
// if itself is the tallest,
// l_max == r_max == height[i]
res += Math.min(l_max, r_max) - height[i];
}
return res;
}
}class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int res = 0;
for (int i = 1; i < n - 1; i++) {
int l_max = 0, r_max = 0;
// find the tallest pillar on the right
for (int j = i; j < n; j++)
r_max = max(r_max, height[j]);
// find the tallest pillar on the left
for (int j = i; j >= 0; j--)
l_max = max(l_max, height[j]);
// if itself is the highest,
// l_max == r_max == height[i]
res += min(l_max, r_max) - height[i];
}
return res;
}
};class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
res = 0
for i in range(1, n - 1):
l_max, r_max = 0, 0
# find the highest pillar on the right
for j in range(i, n):
r_max = max(r_max, height[j])
# find the highest pillar on the left
for j in range(i, -1, -1):
l_max = max(l_max, height[j])
# if itself is the highest,
# l_max == r_max == height[i]
res += min(l_max, r_max) - height[i]
return resfunc trap(height []int) int {
n := len(height)
res := 0
for i := 1; i < n - 1; i++ {
l_max := 0
r_max := 0
// find the tallest pillar on the right
for j := i; j < n; j++ {
r_max = max(r_max, height[j])
}
// find the tallest pillar on the left
for j := i; j >= 0; j-- {
l_max = max(l_max, height[j])
}
// if itself is the highest,
// l_max == r_max == height[i]
res += min(l_max, r_max) - height[i]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}var trap = function(height) {
var n = height.length;
var res = 0;
for (var i = 1; i < n - 1; i++) {
var l_max = 0, r_max = 0;
// find the tallest pillar on the right
for (var j = i; j < n; j++)
r_max = Math.max(r_max, height[j]);
// find the tallest pillar on the left
for (var j = i; j >= 0; j--)
l_max = Math.max(l_max, height[j]);
// if itself is the tallest,
// l_max == r_max == height[i]
res += Math.min(l_max, r_max) - height[i];
}
return res;
};With the previous approach, this solution is quite straightforward and brute-force, with a time complexity of O(N^2) and a space complexity of O(1). However, it's clear that the method of calculating r_max and l_max is very clumsy. A common optimization technique is to use a memoization.
II. Memoization Optimization
In the previous brute-force solution, didn't we have to calculate r_max and l_max at every position i? We can simply precompute the results instead of naively traversing each time, which will reduce the time complexity.
We use two arrays, r_max and l_max, as memoization. l_max[i] represents the height of the tallest pillar to the left of position i, and r_max[i] represents the height of the tallest pillar to the right of position i. By precomputing these two arrays, we avoid redundant calculations:
class Solution {
public int trap(int[] height) {
if (height.length == 0) {
return 0;
}
int n = height.length;
int res = 0;
// the array acts as a memo
int[] l_max = new int[n];
int[] r_max = new int[n];
// initialize the base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// calculate l_max from left to right
for (int i = 1; i < n; i++)
l_max[i] = Math.max(height[i], l_max[i - 1]);
// calculate r_max from right to left
for (int i = n - 2; i >= 0; i--)
r_max[i] = Math.max(height[i], r_max[i + 1]);
// calculate the answer
for (int i = 1; i < n - 1; i++)
res += Math.min(l_max[i], r_max[i]) - height[i];
return res;
}
}class Solution {
public:
int trap(vector<int>& height) {
if (height.size() == 0) {
return 0;
}
int n = height.size();
int res = 0;
// the array acts as a memo
vector<int> l_max(n);
vector<int> r_max(n);
// initialize the base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// calculate l_max from left to right
for (int i = 1; i < n; i++)
l_max[i] = max(height[i], l_max[i - 1]);
// calculate r_max from right to left
for (int i = n - 2; i >= 0; i--)
r_max[i] = max(height[i], r_max[i + 1]);
// calculate the answer
for (int i = 1; i < n - 1; i++)
res += min(l_max[i], r_max[i]) - height[i];
return res;
}
};class Solution:
def trap(self, height: List[int]) -> int:
if len(height) == 0:
return 0
n = len(height)
res = 0
# array as a memo
l_max = [0] * n
r_max = [0] * n
# initialize the base case
l_max[0] = height[0]
r_max[n - 1] = height[n - 1]
# calculate l_max from left to right
for i in range(1, n):
l_max[i] = max(height[i], l_max[i - 1])
# calculate r_max from right to left
for i in range(n - 2, -1, -1):
r_max[i] = max(height[i], r_max[i + 1])
# calculate the answer
for i in range(1, n - 1):
res += min(l_max[i], r_max[i]) - height[i]
return resfunc trap(height []int) int {
if len(height) == 0 {
return 0
}
n := len(height)
res := 0
// array as a memo
l_max := make([]int, n)
r_max := make([]int, n)
// initialize the base case
l_max[0] = height[0]
r_max[n-1] = height[n-1]
// calculate l_max from left to right
for i := 1; i < n; i++ {
l_max[i] = max(height[i], l_max[i-1])
}
// calculate r_max from right to left
for i := n-2; i >= 0; i-- {
r_max[i] = max(height[i], r_max[i+1])
}
// calculate the answer
for i := 1; i < n-1; i++ {
res += min(l_max[i], r_max[i]) - height[i]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}var trap = function(height) {
if (height.length === 0) {
return 0;
}
var n = height.length;
var res = 0;
// the array acts as a memo
var l_max = new Array(n).fill(0);
var r_max = new Array(n).fill(0);
// initialize the base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// calculate l_max from left to right
for (var i = 1; i < n; i++) {
l_max[i] = Math.max(height[i], l_max[i - 1]);
}
// calculate r_max from right to left
for (var i = n - 2; i >= 0; i--) {
r_max[i] = Math.max(height[i], r_max[i + 1]);
}
// calculate the answer
for (var i = 1; i < n - 1; i++) {
res += Math.min(l_max[i], r_max[i]) - height[i];
}
return res;
};This optimization is actually similar to the brute-force approach, but it avoids repeated calculations, reducing the time complexity to O(N), which is optimal. However, the space complexity is O(N). Let's look at a more elegant solution that can reduce the space complexity to O(1).
Three, Two-Pointer Solution
My Advice
This solution is for expanding your thinking; it's good to understand it, but you don't need to be overly obsessed with the optimal solution. For most people, in real interviews or exams, being able to use straightforward methods to tackle problems and write the above solution is sufficient. Although it adds some space complexity, it usually passes on most judging platforms.
Only if you can't pass all test cases and you have extra time after finishing other questions should you spend time optimizing the above solution.
The idea behind this solution is exactly the same, but the implementation is very clever. This time, we won't use a memo to pre-calculate; instead, we'll use two pointers to calculate on the go, saving space complexity.
First, let's look at a part of the code:
int trap(int[] height) {
int left = 0, right = height.length - 1;
int l_max = 0, r_max = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// At this point, what do l_max and r_max represent respectively?
left++; right--;
}
}int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int l_max = 0, r_max = 0;
while (left < right) {
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
// At this point, what do l_max and r_max represent respectively?
left++; right--;
}
}def trap(height: List[int]) -> int:
left, right = 0, len(height) - 1
l_max, r_max = 0, 0
while left < right:
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
# At this point, what do l_max and r_max represent respectively?
left += 1
right -= 1func trap(height []int) int {
left, right := 0, len(height) - 1
l_max, r_max := 0, 0
for left < right {
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
// At this point, what do l_max and r_max represent respectively?
left++
right--
}
}var trap = function(height) {
var left = 0, right = height.length - 1;
var l_max = 0, r_max = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// At this point, what do l_max and r_max represent respectively?
left++; right--;
}
}Regarding this section of the code, what do l_max and r_max represent?
It's quite straightforward: l_max is the height of the tallest pillar in the range height[0..left], and r_max is the height of the tallest pillar in the range height[right..end].
With this understanding, let's directly look at the solution:
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int l_max = 0, r_max = 0;
int res = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// res += min(l_max, r_max) - height[i]
if (l_max < r_max) {
res += l_max - height[left];
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
}
}class Solution {
public:
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int l_max = 0, r_max = 0;
int res = 0;
while (left < right) {
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
// res += min(l_max, r_max) - height[i]
if (l_max < r_max) {
res += l_max - height[left];
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
}
};class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
l_max, r_max = 0, 0
res = 0
while left < right:
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
# res += min(l_max, r_max) - height[i]
if l_max < r_max:
res += l_max - height[left]
#<extend up -250>
#<div class="img-content"><img src="/images/接雨水/5.jpg" alt class="myimage" loading="lazy" photo-swipe="" /></div>
left += 1
else:
res += r_max - height[right]
right -= 1
return resfunc trap(height []int) int {
left, right := 0, len(height) - 1
l_max, r_max := 0, 0
res := 0
for left < right {
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
// res += min(l_max, r_max) - height[i]
if l_max < r_max {
res += l_max - height[left]
left++
} else {
res += r_max - height[right]
right--
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}var trap = function(height) {
let left = 0, right = height.length - 1;
let l_max = 0, r_max = 0;
let res = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// res += min(l_max, r_max) - height[i]
if (l_max < r_max) {
res += l_max - height[left];
// See the image for a visual representation of the process
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
};You see, the core idea is exactly the same as before, just a change in approach but not in substance. However, careful readers might notice some subtle differences in this solution:
In the previous memoization approach, l_max[i] and r_max[i] represent the heights of the tallest pillars in height[0..i] and height[i..end], respectively.
res += Math.min(l_max[i], r_max[i]) - height[i];
But in the two-pointer solution, l_max and r_max represent the heights of the tallest pillars in height[0..left] and height[right..end]. For example, this code snippet:
if (l_max < r_max) {
res += l_max - height[left];
left++;
}
At this point, l_max is the tallest pillar to the left of the left pointer, but r_max is not necessarily the tallest pillar to the right of the left pointer. Can this really give the correct answer?
Actually, the problem should be thought of this way: we only care about min(l_max, r_max). For the situation in the above diagram, we already know l_max < r_max. Whether r_max is the tallest on the right is not important. What matters is that the water height[i] can hold is only related to the difference with the shorter l_max:
This way, the problem of trapping rainwater is solved.
Further Exploration
Next, let's look at a problem very similar to the trapping rainwater problem, LeetCode problem #11, "Container With Most Water":
11. Container With Most Water | 力扣 | LeetCode |
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1] Output: 1
Constraints:
n == height.length2 <= n <= 1050 <= height[i] <= 104
// The function signature is as follows
int maxArea(int[] height);// The function signature is as follows
int maxArea(vector<int> &height);# The function signature is as follows
def maxArea(height: List[int]) -> int:// The function signature is as follows
func maxArea(height []int) int {}// The function signature is as follows
var maxArea = function(height) {}This problem is very similar to the "Trapping Rain Water" problem, and you can completely apply the same approach from the previous article, making it even simpler. The main difference between the two problems is:
The "Trapping Rain Water" problem presents a histogram-like structure where each horizontal coordinate has a width, whereas in this problem, each horizontal coordinate is a vertical line without any width.
In our previous discussion, we spent a lot of time on l_max and r_max to calculate how much water height[i] could hold. In this problem, since height[i] has no width, it becomes much easier to handle.
For example, in the "Trapping Rain Water" problem, if you know the heights of height[left] and height[right], can you calculate how much water can be trapped between left and right?
No, because you don't know the exact amount of water each pillar between left and right can hold. You need to calculate it using l_max and r_max for each pillar.
Conversely, for this problem, if you know the heights of height[left] and height[right], can you calculate how much water can be trapped between left and right?
Yes, because in this problem, the vertical lines have no width, so the amount of water that can be trapped between left and right is:
min(height[left], height[right]) * (right - left)Similar to the "Trapping Rain Water" problem, the height is determined by the smaller value between height[left] and height[right].
The approach to solving this problem is still the two-pointer technique:
Use two pointers, left and right, to move towards the center from both ends. As you move, calculate the area of the rectangle between [left, right], and the maximum area value is the answer.
Let's directly look at the solution code:
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int res = 0;
while (left < right) {
// the area of the rectangle between [left, right]
int cur_area = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, cur_area);
// two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
}class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int res = 0;
while (left < right) {
// the area of the rectangle between [left, right]
int cur_area = min(height[left], height[right]) * (right - left);
res = max(res, cur_area);
// two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
};class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
res = 0
while left < right:
# the area of the rectangle between [left, right]
cur_area = min(height[left], height[right]) * (right - left)
res = max(res, cur_area)
# two-pointer technique, move the lower side
if height[left] < height[right]:
left += 1
else:
right -= 1
return resfunc maxArea(height []int) int {
left, right := 0, len(height)-1
res := 0
for left < right {
// the area of the rectangle between [left, right]
curArea := min(height[left], height[right]) * (right - left)
res = max(res, curArea)
// two-pointer technique, move the lower side
if height[left] < height[right] {
left++
} else {
right--
}
}
return res
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}var maxArea = function(height) {
let left = 0, right = height.length - 1;
let res = 0;
while (left < right) {
// the area of the rectangle between [left, right]
let cur_area = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, cur_area);
// two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
};The code is similar to the problem of trapping rainwater. However, some readers might wonder why the following if statement moves the lower side:
// Two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}It's actually easy to understand because the height of the rectangle is determined by min(height[left], height[right]), which is the shorter side:
If you move the shorter side, that side might become taller, increasing the height of the rectangle, and thus there is a "possibility" that the area of the rectangle will increase. Conversely, if you move the taller side, the height of the rectangle will not increase regardless, so it is impossible to make the area of the rectangle larger.
With this, the problem is also solved.
