42. 接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 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

提示:

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

代码

完整代码

#include <stdbool.h>

int trap(int* height, int heightSize) {
    int water = 0;
    bool needRoute = false;
    int lastLeftIndex = -1;
    int level = 1;
    for (int i = 0; i < heightSize; i++)
    {
        if(height[i] >= level)
        {
            if(height[i] > level)
            {
                needRoute = true;
            }
            if(lastLeftIndex == -1)
            {
            }
            else
            {
                water += (i - lastLeftIndex - 1) > 0 ? (i - lastLeftIndex - 1) : 0;
                if(((i - lastLeftIndex - 1) > 0 ? (i - lastLeftIndex - 1) : 0) > 0)
                {
                    // printf("index %d, level %d\n",i, level);
                    // printf("water += %d \n",(i - lastLeftIndex - 1));
                }
            }
            // printf("index %d, level %d\n",i, level);
            // printf("left wall refresh %d\n",height[i]);
            lastLeftIndex = i;
        }
        if(i == heightSize - 1)
        {
            level++;
            lastLeftIndex = -1;
            if(needRoute)
            {
                needRoute = false;
                i = -1;
            }
        }
    }
    return water;
}

思路分析

  1. 按层遍历:从第一层(高度为 1)开始,逐层扫描,计算每一层的雨水量。
  2. 水位标记:对于每一层,遍历数组,记录当前层的左右墙壁以及水平距离,计算当前层的雨水量。
  3. 累加求和:将每一层的雨水量累加,得到总的雨水量。
  4. 时间复杂度:考虑每一层的遍历,总的时间复杂度为 O(n * h),其中 n 是数组 height 的长度,h 是数组 height 的最大值。

拆解分析

  • 按层遍历:从高度为 1 开始,逐层向上扫描。
  • 水位标记:对于每一层,记录左右墙壁以及水平距离,计算当前层的雨水量。
  • 累加求和:将每一层的雨水量累加,得到总的雨水量。

复杂度分析

  • 时间复杂度:考虑每一层的遍历,总的时间复杂度为 O(n * h),其中 n 是数组 height 的长度,h 是数组 height 的最大值。
  • 空间复杂度O(1),只使用常数级别的额外空间。

结果

在这里插入图片描述

一题多解

双指针法

代码

#define MIN(a,b) ((a) < (b) ? (a) : (b))

int trap(int* height, int heightSize) {
    if (heightSize <= 2) return 0; // 边界情况处理

    int water = 0;
    int left = 0, right = heightSize - 1;
    int lefth = 0, righth = 0;
    int totalsize = 0;

    while (left < right) {
        if (height[left] <= height[right]) { // 左边界小于等于右边界
            if (height[left] >= lefth) {
                lefth = height[left]; // 更新左边界的高度
            } else {
                water += lefth - height[left]; // 累加雨水量
            }
            left++; // 左边界右移
        } else { // 右边界小于左边界
            if (height[right] >= righth) {
                righth = height[right]; // 更新右边界的高度
            } else {
                water += righth - height[right]; // 累加雨水量
            }
            right--; // 右边界左移
        }
    }

    return water;
}

思路分析

  • 双指针法:使用左右两个指针向中间靠拢,分别记录左右两侧的最大高度。
  • 水位标记:遍历数组,通过比较左右两侧的最大高度来确定当前位置能够存储的雨水量。

拆解分析

  • 双指针移动:左右指针向中间移动,同时更新左右两侧的最大高度。
  • 计算存水量:根据左右两侧的最大高度和当前柱子的高度,确定当前位置的存水量。
  • 结束条件:左右指针相遇时结束遍历。

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组 height 的长度。
  • 空间复杂度:O(1),只使用常数级别的额外空间。

结果

在这里插入图片描述

相关推荐

  1. 【困难】42. 雨水

    2024-06-10 06:02:03       30 阅读

最近更新

  1. 浔川画板v5.0——浔川python科技社

    2024-06-10 06:02:03       0 阅读
  2. C# —— for循环语句

    2024-06-10 06:02:03       0 阅读
  3. 鸿蒙开发:【启动本地PageAbility】

    2024-06-10 06:02:03       0 阅读
  4. 地学类期刊最新CiteScore™ 汇总

    2024-06-10 06:02:03       0 阅读
  5. 怎么通过AI构架一个个人简介并且写出来

    2024-06-10 06:02:03       0 阅读

热门阅读

  1. spdlog源码解析

    2024-06-10 06:02:03       3 阅读
  2. Spring Boot集成thymeleaf快速入门demo

    2024-06-10 06:02:03       4 阅读
  3. 排查服务器cpu运行过高

    2024-06-10 06:02:03       6 阅读
  4. go语言切片去重的3种方式总结

    2024-06-10 06:02:03       4 阅读
  5. SpringMVC的执行流程

    2024-06-10 06:02:03       6 阅读
  6. mysql数据库安装_修改密码_忘记密码(修改)

    2024-06-10 06:02:03       4 阅读
  7. Android基础-binder机制

    2024-06-10 06:02:03       5 阅读
  8. Python中的上下文管理器(contextlib)模块

    2024-06-10 06:02:03       7 阅读
  9. ipc-test.bk and mmap is also similar.

    2024-06-10 06:02:03       5 阅读
  10. 补篇协程:susend 挂起函数的深入理解

    2024-06-10 06:02:03       7 阅读