一般般帅
上一篇:记CVTE一道算法题
花样接雨水
2409 2024-05-12 2024-05-13
前言：字节面试经典算法题，难度hard，论接雨水的n种方式！
一、题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [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：
输入：height = [4,2,0,3,2,5]
输出：9
输入：height = [5, 8, 9, 4, 9, 6, 1, 4]
输出：8
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
代码模板：
class Solution {
public int trap(int[] height) {
}
}
Leetcode原题链接：https://leetcode.cn/problems/trapping-rain-water/
二、我的解法
1、思路
假如让我自己去数，我会怎么做？我的想法就是我的思路！
理题：
设定左柱为left、右柱为right。如果left、right能够接雨水，则必须满足下面条件
- left、right之间有空隙（right - left > 1），且空隙之间不能再出现任何一个大于等于 Math.min(left, right) 的柱子。
- left左侧，不能再出现比left大的柱子；right右侧，不能再出现比right大的柱子。
- 当前柱子水 = min(左右两边最高柱子）- 当前柱子高度。
我的思路：
-
先从最左右两端开始去除无效柱子。设定双指针分别为left、right。如果left <= left + 1，则说明left可以往左移动一位；如果right -1 > right，则说明right可以往右移动一位；
-
重复上述步骤，当不能再移动时，说明此时left、right之间已经满足接雨水的前置条件：left是左移以来最大的数，left是右移以来最大的数。
-
此时判断 left、right可以接多少雨水，判断逻辑如下：
- left、right是否存在空隙，且空隙之间找不到任何一个大于等于 Math.min(left, right) 的柱子（不含left、right）。
- 符合上述条件，根据水位 Math.min(left, right) ，统计每个柱子可以接的雨水数。
- 不符合上诉条件，直接返回 0。
-
如果上一步雨水数为0，则固定left不变，right--，跳到最外层循环；如果上一步雨水数大于0，则 left = right，right = 最右侧柱子，跳到最外层循环。
如果看得不是太明白，可以自行带入示例。或者自己先开拓下思路，想一想试一试，然后再看我的可能效果会好一点。
2、AC代码
执行用时分布：432ms，击败5.10%使用 Java 的用户。
消耗内存分布：45.60MB，击败7.89%使用 Java 的用户。
时间复杂度：O(n²)，主要耗时在countTrap方法，含两个关键的for循环。
空间复杂度：O(1)，无额外存储成本。
@Slf4j
public class ThirdWater {
public int trap(int[] height) {
int sum = 0, left = 0, right = height.length - 1;
while (left < right) {
// 去除左边无效柱子
while (left < height.length - 1 && height[left] <= height[left + 1]) {
left++;
}
// 去除右边无效柱子
while (right > 0 && height[right - 1] >= height[right]) {
right--;
}
if (left >= right) {
return sum;
}
int total = countTrap(height, left, right);
if (total > 0) {
sum += total;
left = right;
right = height.length - 1;
} else {
right--;
}
}
return sum;
}
/**
* 计算可以接到的雨滴数，为0则表示无法接到雨滴
*/
public int countTrap(int[] height, int left, int right) {
int sum = 0;
// 有效柱子之间的水位线
int curWaterLevel = Math.min(height[left], height[right]);
while (left < height.length - 1 && height[left + 1] >= curWaterLevel && height[left] >= height[left + 1]) {
left++;
}
while (height[right - 1] >= curWaterLevel && height[right] >= height[right - 1]) {
right--;
}
for (int k = left + 1; k <= right - 1; k++) {
if (height[k] < curWaterLevel) {
sum += (curWaterLevel - height[k]);
} else {
return 0;
}
}
return sum;
}
}
3、测试代码
public static void main(String[] args) {
ThirdWater water = new ThirdWater();
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
water.test(new int[]{5, 1, 3}, 2);
water.test(new int[]{3,2,1,2}, 1);
water.test(new int[]{5, 8, 9, 4, 9, 6, 1, 4}, 8);
water.test(new int[]{4,2,0,3,2,5}, 9);
water.test(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}, 6);
water.test(new int[]{4,4,4,7,1,0}, 0);
water.test(new int[]{1, 7, 8}, 0);
water.test(new int[]{0,0,0,2,0,8,6,7,7}, 3);
water.test(new int[]{1000,999,998,997,996,995,994,993,992,991,990,989,988,987,986,985,984,983,982,981,980,979,978,977,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966,966},
0);
}
// 执行3次 22ms 27ms 20ms
System.out.println("执行总耗时=" + (System.currentTimeMillis() - start) + "ms");
}
private void test(int[] arr, int expect) {
// log.info("开始测试:" + Arrays.toString(arr));
int result = trap(arr);
if (result != expect) {
throw new RuntimeException("测试不通过, 期望=" + expect + " 实际=" + result + " arr={}" + Arrays.toString(arr));
}
}
三、大神解法
基于Leetcode大神解法，有略微改动。
1、按行求
大神思路：求第 i 层的水，遍历每个位置，如果当前的高度小于 i，并且两边有高度大于等于 i 的，说明这个地方一定有水，水就可以加 111。
时间复杂度：如果最大的数是 m，个数是 n，那么就是 O(m∗n)。
空间复杂度：O(1)。
我的看法：很巧妙的一种思路，如果不是官方给了一个极端case阻碍AC（输入数据为1-10000，即最大行高为10000），不失为一种经典解法。
// AC不了，报执行超时
public int trap(int[] height) {
int sum = 0;
// 找到最大的高度，以便遍历
int max = getMax(height);
// 如果行数足够高，这一步的效率太低了，比如 10000 0 10000 1 10000
for (int i = 1; i <= max; i++) {
// 标记是否开始更新 temp
boolean isStart = false;
int temp_sum = 0;
for (int j = 0; j < height.length; j++) {
if (isStart && height[j] < i) {
temp_sum++;
}
if (height[j] >= i) {
sum = sum + temp_sum;
temp_sum = 0;
isStart = true;
}
}
}
return sum;
}
private int getMax(int[] height) {
int max = 0;
for (int i = 0; i < height.length; i++) {
if (height[i] > max) {
max = height[i];
}
}
return max;
}
2、按列求
大神思路：遍历每一列，然后分别求出这一列两边最高的墙。找出较矮的一端，和当前列的高度比较，结果就是上边的三种情况。
时间复杂度：O(n²)，遍历每一列需要 n，找出左边最高和右边最高的墙加起来刚好又是一个 n，所以是 n²。
空间复杂度：O(1)。
我的看法：很清晰明了的一种解法，但是貌似效率不太行。
// 我的
// 执行用时分布：432ms，击败5.10%使用 Java 的用户
// 消耗内存分布：45.60MB，击败7.89%使用 Java 的用户
// 按列求
// 执行用时分布：660ms，击败5.00%使用 Java 的用户
// 消耗内存分布：45.52MB，击败17.21%使用 Java 的用户
public int trap(int[] height) {
int sum = 0;
// 最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
for (int i = 1; i < height.length - 1; i++) {
int max_left = 0;
// 找出左边最高
for (int j = i - 1; j >= 0; j--) {
if (height[j] > max_left) {
max_left = height[j];
}
}
int max_right = 0;
// 找出右边最高
for (int j = i + 1; j < height.length; j++) {
if (height[j] > max_right) {
max_right = height[j];
}
}
// 找出两端较小的
int min = Math.min(max_left, max_right);
// 只有较小的一段大于当前列的高度才会有水，其他情况不会有水
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
3、动态规划
大神思路：解法二中。对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。
时间复杂度：O(n)。
空间复杂度：O(n)，用来保存每一列左边最高的墙和右边最高的墙。
我的看法：典型的空间换时间，算法的本质就是空间和时间的互相转化。另外，动态规划永远的神，配合 Math.max + 数组下标让人佩服不已。
// 我的，本地执行循环玩一万次，都是在20ms左右
// 执行用时分布：432ms，击败5.10%使用 Java 的用户
// 消耗内存分布：45.60MB，击败7.89%使用 Java 的用户
// 动态规划，本地执行循环玩一万次，都是在40ms左右，应该是空间复杂度上升导致的
// 执行用时分布，1ms，击败69.01%使用 Java 的用户
// 消耗内存分布，44.95MB，击败55.55%使用 Java 的用户
public int trap(int[] height) {
int sum = 0;
// max_left [i] 代表第 i 列左边最高的墙的高度
// 第 i 列左（右）边最高的墙，是不包括自身的
int[] max_left = new int[height.length];
// max_right[i] 代表第 i 列右边最高的墙的高度
int[] max_right = new int[height.length];
for (int i = 1; i < height.length - 1; i++) {
max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
}
for (int i = height.length - 2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(max_left[i], max_right[i]);
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
4、动态规划优化版
// 对于 max_left 的循环，可以进行简化
public int trap(int[] height) {
int sum = 0;
int max_left = 0;
int[] max_right = new int[height.length];
for (int i = height.length - 2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
max_left = Math.max(max_left, height[i - 1]);
int min = Math.min(max_left, max_right[i]);
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
5、双指针
// 真tm神奇，代入示例阅读效果更佳
public int trap2(int[] height) {
int n = height.length;
int res = 0;
// 左右指针：分别指向左右两边界的列
int left = 0, right = n - 1;
// 左指针的左边最大高度、右指针的右边最大高度
int leftMax = height[left], rightMax = height[right];
// 最两边的列存不了水
left++;
right--;
// 向中间靠拢
while (left <= right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
// 左指针的leftMax比右指针的rightMax矮
// 说明：左指针的右边至少有一个板子 > 左指针左边所有板子
// 根据水桶效应，保证了左指针当前列的水量决定权在左边
// 那么可以计算左指针当前列的水量：左边最大高度-当前列高度
res += (leftMax - height[left]);
left++;
} else {
// 右边同理
res += (rightMax - height[right]);
right--;
}
}
return res;
}
6、栈
public int trap6(int[] height) {
int sum = 0;
Stack<Integer> stack = new Stack<>();
int current = 0;
while (current < height.length) {
//如果栈不空并且当前指向的高度大于栈顶高度就一直循环
while (!stack.empty() && height[current] > height[stack.peek()]) {
int h = height[stack.peek()]; //取出要出栈的元素
stack.pop(); //出栈
if (stack.empty()) { // 栈空就出去
break;
}
int distance = current - stack.peek() - 1; //两堵墙之前的距离。
int min = Math.min(height[stack.peek()], height[current]);
sum = sum + distance * (min - h);
}
stack.push(current); //当前指向的墙入栈
current++; //指针后移
}
return sum;
}
不过如此，打完收工！
总访问次数: 48次, 一般般帅 创建于 2024-05-12, 最后更新于 2024-05-13
欢迎关注微信公众号，第一时间掌握最新动态！