当前位置: 首页 > 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在…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...