力扣接雨水

news/2024/9/17 2:06:39/ 标签: leetcode, 算法, 数据结构

给定 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

提示:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

 动态规划:

class Solution {public int trap(int[] height) {int len = height.length;// 如果数组长度为0,返回0if(len == 0){return 0;}// 创建一个数组用于存储每个位置左侧的最大高度int[] leftMax = new int[len];for(int i = 1; i < len; i++){// 更新当前点的左侧最大高度leftMax[i] = Math.max(height[i-1], height[i]);}// 创建一个数组用于存储每个位置右侧的最大高度int[] rightMax = new int[len];for(int i = len-2; i >= 0; i--){// 更新当前点的右侧最大高度rightMax[i] = Math.max(height[i], height[i+1]);}int ans = 0;// 计算每个位置能够存储的水量for(int i = 0; i < len; i++){ans += Math.min(leftMax[i], rightMax[i]) - height[i];}// 返回能够存储的总水量return ans;}
}

单调栈解决

import java.util.Stack;class Solution {public int trap(int[] height) {// 初始化总雨水量为0int totalWater = 0;// 创建一个栈用于存储数组索引Stack<Integer> stack = new Stack<>();// 遍历每个高度for (int i = 0; i < height.length; i++) {// 当栈非空且当前高度大于栈顶所指的高度时while (!stack.isEmpty() && height[i] > height[stack.peek()]) {// 取出栈顶的高度索引int top = stack.pop();// 如果栈为空,跳出循环if (stack.isEmpty()) {break;}// 计算当前柱子的宽度int distance = i - stack.peek() - 1;// 计算能形成的水位高度差int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];// 计算当前能积的水量并加到总水量中totalWater += distance * boundedHeight;}// 将当前索引入栈stack.push(i);}// 返回总雨水量return totalWater;}
}

工作原理

  1. 单调递减栈:栈中存储的是高度数组的索引。栈内元素对应的高度从栈底到栈顶是非递增的。
  2. 遍历高度数组:对于每一个高度,若其大于栈顶元素所指的高度(即找到一个可能的凹槽),则计算当前凹槽的水量。
  3. 水量计算
    • 宽度:凹槽宽度为当前索引 i 与栈顶下一个元素的索引之差再减去 1。
    • 高度:水位高度差为 min(当前高度, 栈顶下一个高度) - 栈顶高度
  4. 累加水量:将计算出的水量累加到总水量中。

在计算接雨水的过程中,水的高度取决于柱子之间的最低高度。具体来说,水只能被较矮的柱子挡住。因此,关键在于找到最低的柱子,并根据它来计算可能存储的水量。

class Solution {public int trap(int[] height) {int len=height.length;int left=0,right=len-1;int leftMax=0,rightMax=0;int ans=0;while(left<=right){leftMax=Math.max(leftMax,height[left]);rightMax=Math.max(rightMax,height[right]);if(height[left]<height[right]){ans+=leftMax-height[left];left++;}else{ans +=rightMax-height[right];right--;}}return ans;}
}

判断逻辑

  1. 水量计算基础

    • 对于 height[left] < height[right] 的情况,由于 leftMax 是从左侧移动过程中遇到的最大高度,而 rightMax 是从右侧移动过程中遇到的最大高度,因此:
      • 当前柱子 height[left] 左侧的最大高度 leftMax 是可靠的。
      • 但是,右侧的最大高度 rightMax 还可能会更新。因此,此时计算 left 位置的积水量是安全的。
  2. 为什么选择较小的高度

    • 如果 height[left] < height[right],意味着在当前位置 left,其右侧有更高的柱子。这个较高的柱子可以帮助挡住雨水。因此可以确定 leftMax 是最小的限制条件,用它来计算当前位置可能存储的水量是安全的。
    • 如果 height[left] >= height[right],那么右侧柱子在此时成为决定因素,左侧的 leftMax 没有影响,应该通过 rightMax 计算右侧的水量。

例子说明

假设 height[left] = 2height[right] = 5

  • left 侧低于 right:可以确定在左侧 left 柱子能容纳的水量只取决于 leftMax。因此,将 left 向右移动并计算 leftMax - height[left]

  • 如果反过来:如果左侧高于或等于右侧,则右侧可能会积水,因此移动 right 向左并计算 rightMax - height[right]

总结

这一判断的核心在于:

  • 小于:左侧可能有积水,计算左侧。
  • 大于等于:右侧可能有积水,计算右侧。

初始状态下的 right 指针

  • right 指针初始位置:它从数组的最右端开始。
  • left 指针初始位置:它从数组的最左端开始。

初始比较:height[left] < height[right]

算法的开始阶段,我们用 height[left] < height[right] 来判断接下来的行动。虽然 right 一开始位于数组的最右边,但这并不影响算法的正确性,原因如下:

  1. rightMax 的初始化

    • 初始时,rightMax 会等于 height[right]。因为 right 指针在最右端,所以 rightMax 一开始就是数组最右边的那个高度。
    • 随着 right 指针向左移动,rightMax 会逐渐更新为更大的值,直到遍历完所有右边的柱子。
  2. 初始状态的判断

    • 在开始时,算法leftright 的柱子高度进行比较。
    • 如果 height[left] < height[right],说明左边的柱子比右边矮。在这种情况下,右边更高的柱子可以“挡住”水,因此左边柱子上方可能会有积水,这时候左边的积水高度是可以确定的,所以移动 left 指针并计算水量。
    • 如果 height[left] >= height[right]算法会移动 right 指针。此时,不会计算 left 指针位置的积水,而是继续查看右边的柱子是否可能形成积水。
  3. 意义在于确定安全的水量

    • 通过比较 height[left]height[right]算法确保了在当前位置计算水量时,有足够的信息保证水量是准确的。
    • rightMaxleftMax算法执行过程中不断更新,确保算法总是在安全的条件下进行计算。

实际意义

即使 right 指针最开始位于最右边,这个初始比较也有意义,因为它为整个算法奠定了基础。我们可以通过这个初始比较,确保在移动 leftright 指针时,计算的积水量是正确且安全的。

举个例子

假设 height 数组为 [1, 0, 2, 1, 0, 1, 3]leftright 初始分别在位置 06

  • left 开始为 1right 开始为 3
  • 第一次比较时,height[left] = 1height[right] = 3,显然 1 < 3,我们可以放心地移动 left 指针,因为左边的积水高度确定不会超过 leftMax

总之,这一步比较对于算法的正确性和水量计算至关重要,即使 right 指针最初处于最右边,也依然有效且必要。


http://www.ppmy.cn/news/1522052.html

相关文章

15 用户管理

如果我们只能使用root用户&#xff0c;这样存在安全隐患。这时&#xff0c;就需要使用mysql的用户管理 张三只能操纵mytest这个库&#xff0c;李四只能操纵msg这个库&#xff0c;如果给他们root账户&#xff0c;就可以操纵所有库&#xff0c;风险太大 用户 用户信息 用户都存…

AI基础 L4 Uninformed Search I 无信息搜索

Problem-solving agent • Deterministic, fully observable ⇒ single-state problem Agent knows exactly which state it will be in; solution is a sequence • Non-observable ⇒ conformant problem Agent may have no idea where it is; solution (if any) is a sequen…

数据库系统 第40节 数据库安全策略

数据库安全策略是确保数据库系统安全、防止数据泄露和未授权访问的关键措施。以下是一些常见的数据库安全策略&#xff0c;以及它们在实际应用中的一些示例。 1. 访问控制 访问控制是数据库安全的基础&#xff0c;它确保只有授权用户才能访问数据库资源。这通常通过以下方式实…

【开源免费】基于SpringBoot+Vue.JS高校校园招聘服务系统(JAVA毕业设计)

本文项目编号 T 010 &#xff0c;文末自助获取源码 \color{red}{T010&#xff0c;文末自助获取源码} T010&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…

利用Stable Diffusion AI图像模型评估智能车模型算法表现(下篇)

今天小李哥将介绍亚马逊云科技的Jupyter Notebook机器学习托管服务Amazon SageMaker上&#xff0c;通过AI图像生成模型Stable Diffusion Upscale和Depth、向量知识库和LangChain Agent&#xff0c;生成用于AI 智能车模型训练的图像数据集并评估模型表现。 本系列共分为上下两篇…

Math Reference Notes: 三角函数术语的几何学解释

在三角函数中&#xff0c;“正”、“余”、“弦”、"割"这些词汇源自古代的几何学术语&#xff0c;它们与三角形的边和角的关系密切相关。 1. 弦&#xff08;sin&#xff0c;cos的含义&#xff09;&#xff1a; “弦”字来源于圆中的“弦线”&#xff0c;即连接圆周…

VUE2.0 elementUI el-input-number 数据更新,视图不更新——基础积累

今天遇到一个问题&#xff0c;是关于el-input-number组件的&#xff0c;发现数据明明已经更改了&#xff0c;但是页面上组件输入框中还是之前的值。 比如上方输入框中&#xff0c;我输入120.5&#xff0c;就会出现下面的诡异现象 回显此值是120.779&#xff0c;但是页面上输入…

小阿轩yx-云原生存储Rook部署Ceph

小阿轩yx-云原生存储Rook部署Ceph 前言 Rook 一款云原生存储编排服务工具由云原生计算基金会&#xff08;CNCF&#xff09;孵化&#xff0c;且于2020年10月正式进入毕业阶段。并不直接提供数据存储方案&#xff0c;而是集成了各种存储解决方案&#xff0c;并通过一种自管理、…

log4j2 与 log4j使用时的几点小区别 - log4j2上手说明

虽然log4j2 目前还是beta版&#xff0c;不过OneCoder已经忍不住要尝试一下。跟使用log4j 比起来&#xff0c;上手上主要的区别有。 1、依赖的jar包。使用slf4jlog4j2 时&#xff0c;依赖的jar包如下&#xff1a;( gradle配置&#xff0c;Maven对照修改即可) dependencies{ com…

(二十六)Java 数据结构

目录 一. 前言 二. 枚举&#xff08;Enumeration&#xff09; 三. 位集合&#xff08;BitSet&#xff09; 四. 向量&#xff08;Vector&#xff09; 五. 栈&#xff08;Stack&#xff09; 六. 字典&#xff08;Dictionary&#xff09; 七. 哈希表&#xff08;Hashtable&…

『功能项目』Unity本地数据库读取进入游戏【29】

本章项目成果展示 打开上一篇28Unity连接读取本地数据库的项目&#xff0c; 本章要做的事情是通过读取本地数据库登录进入游戏场景 首先创建一个脚本文件夹&#xff1a; 新建脚本&#xff1a;MySqlAccess.cs 编写脚本&#xff1a;MySqlAccess.cs using UnityEngine; using MyS…

【无人机设计与控制】 四轴飞行器的位移控制

摘要 本文介绍了一种四轴飞行器的位移控制方法&#xff0c;并通过Simulink模型进行仿真和验证。该方法通过PID控制器对飞行器的位移进行精确调节&#xff0c;以实现飞行器在三维空间中的稳定定位和路径跟踪。通过参数调节&#xff0c;能够适应不同的飞行任务需求&#xff0c;确…

Maven持续集成(Continuous integration,简称CI)版本友好管理

从Maven 3.5.0-beta-1 版本开始可以在pom文件中使用 r e v i s i o n 、 {revision}、 revision、{sha1}、${changelist}做为版本的占位符。 一、单module简单使用${revision}的场景 <project><modelVersion>4.0.0</modelVersion><parent><groupId…

使用 Cloudflare R2 代替 AWS S3……

欢迎来到雲闪世界。目录 1. AWS S3 与 Cloudflare R2 2.什么是 AWS S3&#xff1f; 3.什么是 Cloudflare R2&#xff1f; 4. AWS S3 定价 ∘ AWS S3 定价详情 (美国东部 - 弗吉尼亚北部地区) 5. Cloudflare R2 定价 ∘ Cloudflare R2 定价详情 (美国地区) 6.免费套餐&#xff…

Patlibc———更快捷的更换libc

起初是为了简化做pwn题目时&#xff0c;来回更换libc的麻烦&#xff0c;为了简化命令&#xff0c;弄了一个小脚本&#xff0c;可以加入到/usr/local/bin中&#xff0c;当作一个快捷指令&#x1f522; 这个写在了tools库&#xff08;git clone https://github.com/CH13hh/tools…

数据分析:numpy02

目录 1、NumPy 切片和索引 2、数组元素的添加与删除 3、修改数组形状 4、numpy随机数 1、NumPy 切片和索引 ndarray对象的内容可以通过索引或切片来访问和修改&#xff0c;与 Python 中 列表list 的切片操作一样。 ndarray 数组可以基于 0 - n 的下标进行索引&#xff0c;切片…

Redis位图BitMap

一、为什么使用位图&#xff1f; 使用位图能有效实现 用户签到 等行为&#xff0c;用数据库表记录签到&#xff0c;将占用很多存储&#xff1b;但使用 位图BitMap&#xff0c;就能 大大减少存储占用 二、关于位图 本质上是String类型&#xff0c;最小长度8位&#xff08;一个字…

k8s API资源对象

API资源对象Deployment 最小的资源是pod&#xff0c;deployment是多个pod的集合&#xff08;多个副本实现高可用、负载均衡等&#xff09;。 使用yaml文件来配置、部署资源对象。 Deployment YAML示例&#xff1a; vi ng-deploy.yaml apiVersion: apps/v1 kind: Deployment…

JS设计模式之“分即是合” - 建造者模式

引言 当我们在进行软件编程时&#xff0c;常常会遇到需要创建复杂对象的情况。这些对象可能有多个属性&#xff0c;属性之间存在依赖关系&#xff0c;或需要按照特定的骤来创建。在这种情况下&#xff0c;使用建造者模式&#xff08;Builder Pattern&#xff09;可以提供一种活…

给A的平方根矩阵乘高斯随机向量

所以给A的平方根矩阵乘高斯随机向量&#xff0c;目的是得到很多矩阵&#xff0c;这些矩阵的空间平均 A