长沙九度网络科技_上海网页美工设计_软文写作技巧有哪些_江苏疫情最新消息

题目介绍

解法

法一：通过计算每个位置 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;}
}