#P4006. 接雨水
-
ID: 2208
Tried: 231
Accepted: 98
Difficulty: 6
接雨水
题目内容
给定n个非负整数表示每个宽度为 1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入描述
输入共两行。
-
第一行为两个个整数n，代表数组height的长度。
-
第二行为n个整数height0,height1,...,heightn−1，数字之间以空格分隔。
输出描述
一个整数，表示答案。
样例1
输入
12
0 1 0 2 1 0 1 3 2 1 2 1
输出
6
说明
上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接6个单位的雨水（蓝色部分表示雨水）
样例2
输入
6
4 2 0 3 2 5
输出
9
提示
- n==height.length
- 1<=n<=2∗104
- 0<=height[i]<=105
接雨水
题目分析
给定一组柱子高度的数组 height，需要计算这些柱子之间能够接住的雨水总量。直观来看，每个柱子上方能够存多少雨水，取决于其左右两侧的最高柱子的高度。
解题思路
本题可以使用 双指针法 进行求解，主要思路如下：
- 维护两个指针
left和right，分别指向数组的左右两端。 - 维护两个变量
left_max和right_max，分别表示当前位置左侧和右侧的最大高度。 - 如果
height[left] < height[right]，说明left侧的最大值决定了left位置能接多少水：- 如果
height[left] >= left_max，更新left_max。 - 否则，当前位置能够接
left_max - height[left]单位的水。 left指针右移。
- 如果
- 反之，如果
height[right] <= height[left]，说明right侧的最大值决定了right位置能接多少水：- 如果
height[right] >= right_max，更新right_max。 - 否则，当前位置能够接
right_max - height[right]单位的水。 right指针左移。
- 如果
- 继续上述过程，直到
left和right相遇。
复杂度分析
- 由于整个数组只遍历了一遍，时间复杂度为 O(n)。
- 只使用了常数级别的额外空间，空间复杂度为 O(1)。
代码实现
Python 代码
class Solution:
def trap(self, height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water
# 读取输入并处理
if __name__ == "__main__":
n = int(input())
height = list(map(int, input().split()))
solution = Solution()
print(solution.trap(height))
Java 代码
import java.util.Scanner;
public class Main {
public class Solution {
public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] height = new int[n];
for (int i = 0; i < n; i++) {
height[i] = scanner.nextInt();
}
scanner.close();
Main main = new Main();
Solution solution = main.new Solution();
System.out.println(solution.trap(height));
}
}
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
if (height.empty()) return 0;
int left = 0, right = height.size() - 1;
int left_max = 0, right_max = 0;
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
} else {
water += left_max - height[left];
}
left++;
} else {
if (height[right] >= right_max) {
right_max = height[right];
} else {
water += right_max - height[right];
}
right--;
}
}
return water;
}
};
int main() {
int n;
cin >> n;
vector<int> height(n);
for (int i = 0; i < n; i++) {
cin >> height[i];
}
Solution solution;
cout << solution.trap(height) << endl;
return 0;
}