当前位置: 首页 > news >正文

LeetCode 42. 接雨水(动态规划 / 单调栈)

题目:

链接:LeetCode 42. 接雨水
难度:困难

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

方法一:

动态规划:

按列求每一列能存的雨水时,应该求这一列左右最高的墙,其中较矮的墙与这一列高度的差值(>0)为当前列能存的雨水量。对于求左右最高的墙,我们可以用动态规划的方法做:

首先用两个数组,max_left [i] 代表第 i 列左边最高的墙的高度,max_right[i] 代表第 i 列右边最高的墙的高度。(一定要注意下,第 i 列左(右)边最高的墙,是不包括自身的)

对于 max_left我们其实可以这样求。

max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的,就是当前列左边最高的墙了。

对于 max_right我们可以这样求。

max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的,就是当前列右边最高的墙了。

得到了左右最高墙的结果,我们再用前面提到的方法按列求雨水量即可。

代码一:

class Solution {
public:int trap(vector<int>& height) {int n = height.size();int maxleft[n], maxright[n];maxleft[0] = 0, maxright[n - 1] = 0;for(int i = 1; i < n; i++){maxleft[i] = max(maxleft[i - 1], height[i - 1]);}for(int i = n - 2; i >= 0; i--){maxright[i] = max(maxright[i + 1], height[i + 1]);}int sum = 0;for(int i = 1; i < n - 1; i++){int num = min(maxleft[i], maxright[i]) - height[i];if(num > 0) sum += num;}return sum;}
};

时间复杂度O(N)。
空间复杂度O(N)。

方法二:

单调栈:

除了计算并存储每个位置两边的最大高度以外,也可以用单调栈计算能接的雨水总量。

维护一个单调栈,单调栈存储的是下标,满足从栈底到栈顶的下标对应的数组 height 中的元素递减。

从左到右遍历数组,遍历到下标 iii 时,如果栈内至少有两个元素,记栈顶元素为 top,top 的下面一个元素是 left,则一定有 height[left] ≥ height[top]。如果 height[i] > height[top],则得到一个可以接雨水的区域,该区域的宽度是 i−left−1,高度是 min⁡(height[left], height[i]) − height[top],根据宽度和高度即可计算得到该区域能接的雨水量。

为了得到 left,需要将 top 出栈。在对 top 计算能接的雨水量之后,left 变成新的 top,重复上述操作,直到栈变为空,或者栈顶下标对应的 height 中的元素大于或等于 height[i]。

在对下标 i 处计算能接的雨水量之后,将 i 入栈,继续遍历后面的下标,计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。

代码二:

class Solution {
public:int trap(vector<int>& height) {int n = height.size();stack<int> s;  // 单调栈int sum = 0;for(int i = 0; i < n; i++){while(!s.empty() && height[i] > height[s.top()]) {int bottom = height[s.top()];s.pop();int left, left_i;if(s.empty()) {left = 0;left_i = 0;}else {left = height[s.top()];left_i = s.top();}int wallHeight = min(left, height[i]);int num = (wallHeight - bottom) * (i - left_i - 1);if(num > 0) sum += num;}s.emplace(i);}return sum;}
};

时间复杂度O(N),N是数组 height 长度,每个元素只会入栈和出栈一次。
空间复杂度O(N),栈空间最多为N。

相关文章:

LeetCode 42. 接雨水(动态规划 / 单调栈)

题目&#xff1a; 链接&#xff1a;LeetCode 42. 接雨水 难度&#xff1a;困难 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2…...

顺序表、链表刷题指南(力扣OJ)

目录 前言 题目一&#xff1a;删除有序数组中的重复项 思路&#xff1a; 题解&#xff1a; 题目二&#xff1a;合并两个有序数组 思路&#xff1a; 分析&#xff1a; 题解&#xff1a; 题目三&#xff1a;反转链表 思路&#xff1a; 分析&#xff1a; 题解&#xff1a; 题目四&…...

Lambda表达式总结

Lambda作为Java8的新特性&#xff0c;本篇文章主要想总结一下常用的一下用法和api 1.接口内默认方法实现 public interface Formula {double calculate(int a);// 默认方法default double sqrt(int a) {return Math.sqrt(a);} }public static void main(String[] args) {Form…...

岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合&#xff0c;这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0&#xff08;代表水&#xff09;包围着。 岛屿的面积是岛上值为 1 …...

迭代器模式(Iterator)

迭代器模式是一种行为设计模式&#xff0c;可以在不暴露底层实现(列表、栈或树等)的情况下&#xff0c;遍历一个聚合对象中所有的元素。 Iterator is a behavior design pattern that can traverse all elements of an aggregate object without exposing the internal imple…...

Goland搭建远程Linux开发

Windows和Linux都需要先构建好go环境&#xff0c;启用ssh服务。 打开Windows上的Goland&#xff0c;建立项目。 点击添加配置&#xff0c;选择go构建 点击运行于&#xff0c;选择ssh 填上Linux机器的IP地址和用户名 输入密码 没有问题 为了不让每次运行程序和调试程序都生…...

react中PureComponent的理解与使用

一、作用 它是一个纯组件&#xff0c;会做一个数据的浅比较&#xff0c;当props和state没改变的时候&#xff0c;不会render重新渲染&#xff0c; 改变后才会render重新渲染&#xff0c;提高性能。 二、使用 三、注意 它不能和shouldComponentUpdate生命周期同时使用。因为它…...

洛谷——P5714 【深基3.例7】肥胖问题

文章目录 题目题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示 AC代码 题目 题目描述 BMI 指数是国际上常用的衡量人体胖瘦程度的一个标准&#xff0c;其算法是 m h 2 \dfrac{m}{h^2} h2m​&#xff0c;其中 m m m 是指体重&am…...

Mac隐藏和显示文件

由于之前没有使用过Mac本&#xff0c;所以很多地方都不太清楚&#xff0c;在下载git项目的时候&#xff0c;发现没有.git文件&#xff0c; 一开始还以为下载错了&#xff0c;但是git命令是可以看到远端分支以及当前分支的&#xff0c;之后在一次解压文件的时候发现&#xff0c;…...

软件工程中应用的几种图辨析

【软件工程】软件工程中应用的几种图辨析&#xff1a;系统流程图、数据流图、数据字典、实体联系图、状态转换图、层次方框图、Warnier图、IPO图、层次图、HIPO图、结构图、程序流程图、盒图、PAD图、判定表_眩晕李的博客-CSDN博客 软件工程——实体关系图 状态转换图 数据流…...

下载离线版的VS Visual Studio 并下载指定的版本

一、先下载引导程序 下载地址VS VisualStudio官网 在这个页面翻到最下面 在这里下载需要的版本 下载引导程序 二、下载离线安装包 写一个批处理文件&#xff08;vs.bat&#xff09; 命令格式如下 <vs引导程序exe> --layout <离线安装包下载的路径> --add <功能…...

Eureka 学习笔记5:InstanceRegistry

版本 awsVersion ‘1.11.277’ LeaseManager 接口管理实例的租约信息&#xff0c;提供以下功能&#xff1a; 注册实例取消注册实例实例续约剔除过期实例 public interface LeaseManager<T> {/** 注册实例并续约*/void register(T r, int leaseDuration, boolean isRep…...

System Verilog——虚方法的使用

1、使用虚方法目的 通过在父类里定义虚方法(task or function)&#xff0c;可以在当父类句柄调用一个方法时候&#xff0c;前提是若是这个句柄指向了子类对象&#xff0c;则调用的方法为子类的方法而不是父类的方法。 1.1、实例理解&#xff1a;将子类句柄赋值成父类句柄 mod…...

线性规划和单纯形法-原理篇

文章目录 引言线性规划标准型问题特点单纯形法 引言 很多运筹学的教材都是从线性规划开始的&#xff0c;我平时做算法策略的落地应用时也研发了一部分基于线性规划的技术方案。可以说&#xff0c;如果搞不懂线性规划&#xff0c;很难成为一名优秀的运筹优化算法工程师。 但是…...

FBX SDK开发快速上手指南

一段时间以来&#xff0c;我一直想制作一个 FBX Exporter 将 FBX 文件转换为我自己的格式。 整个过程不是很顺利&#xff0c;主要是FBX的官方文档不是很清楚。 另外&#xff0c;由于 FBX 格式被许多应用程序使用&#xff0c;而不仅仅是游戏引擎&#xff0c;因此提供的示例代码没…...

探讨|使用或不使用机器学习

动动发财的小手&#xff0c;点个赞吧&#xff01; 机器学习擅长解决某些复杂问题&#xff0c;通常涉及特征和结果之间的困难关系&#xff0c;这些关系不能轻易地硬编码为启发式或 if-else 语句。然而&#xff0c;在决定 ML 是否是当前给定问题的良好解决方案时&#xff0c;有一…...

Git笔记--Ubuntu上传本地项目到github

目录 1--基本配置 2--本地上传 1--基本配置 ① 创建ssh-key cd ~/.sshssh-keygen -t rsa -C "邮箱地址"② 查看并关联ssh-key gedit id_rsa.pub 复制内容&#xff0c;在 GitHub 中依次点击 Settings -> SSH and GPG keys -> New SSH key&#xff0c;将 id…...

基于Go编写一个可视化Navicat本地密码解析器

前提 开发小组在测试环境基于docker构建和迁移一个MySQL8.x实例&#xff0c;过程中大意没有记录对应的用户密码&#xff0c;然后发现某开发同事本地Navicat记录了根用户&#xff0c;于是搜索是否能够反解析Navicat中的密码掩码&#xff08;这里可以基本断定Navicat对密码是采用…...

Maven【入门笔记】

Maven 解决版本依赖的问题 https://www.liaoxuefeng.com/wiki/1252599548343744/1309301146648610 如果没有项目管理工具&#xff0c;在开发项目的时候&#xff0c;我们需要手动管理依赖包&#xff0c;需要管理依赖包的版本、去找到并下载依赖包、还有依赖包所依赖的包 等等。…...

Android Studio中使用cmake开发JNI实战

JNI学习大纲 一、JNI编程入门 二、Android Studio中使用cmake开发JNI实战 第一章节我们介绍了JNI的开发步骤&#xff0c;那这一章节我们就开始在Android Studio中实战一下吧&#xff0c;Lets Start。 1. Android Studio中安装CMake插件 AS中菜单栏选择Tools>SDK Manager在…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...