文章目录
- 题目介绍
- 解法
题目介绍
解法
法一:通过计算每个位置 i 能够捕获的雨水量,然后将他们相加。
具体做法是:创建两个数组:preMax
和 sufMax
分别用来存储每个位置左边和右边的最大高度,则每个位置 i 可以捕获的雨水量为:Math.min(preMax[i], sufMax[i]) - height[i]
class Solution {public int trap(int[] height) {int n = height.length;int[] preMax = new int[n]; // preMax[i] 表示从 height[0] 到 height[i] 的最大值preMax[0] = height[0];for (int i = 1; i < n; i++) {preMax[i] = Math.max(preMax[i - 1], height[i]);}int[] sufMax = new int[n]; // sufMax[i] 表示从 height[i] 到 height[n-1] 的最大值sufMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {sufMax[i] = Math.max(sufMax[i + 1], height[i]);}int ans = 0;for (int i = 0; i < n; i++) {ans += Math.min(preMax[i], sufMax[i]) - height[i]; // 累加每个水桶能接多少水}return ans;}
}
法二:相向双指针
class Solution {public int trap(int[] height) {int ans = 0;int left = 0;int right = height.length - 1;int preMax = 0; // 前缀最大值,随着左指针 left 的移动而更新int sufMax = 0; // 后缀最大值,随着右指针 right 的移动而更新while (left < right) {preMax = Math.max(preMax, height[left]);sufMax = Math.max(sufMax, height[right]);ans += preMax < sufMax ? preMax - height[left++] : sufMax - height[right--];}return ans;}
}