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

力扣42.接雨水(java,暴力法、前缀和解法)

Problem: 42. 接雨水

文章目录

  • 思路
  • 解题方法
  • 复杂度
  • Code

思路

要能接住雨水,感性的认知就是要形成一个“下凹区域”,则此时我们就要比较当前柱子和其左右柱子高度的关系,易得一个关键的式子:当前小区域的积水 = min(当前柱子左侧最高柱子高度,当前柱子右侧最高柱子高度) - 当前柱子高度;但我们也应当注意按上式得出的结果当前小区域的积水可能为负值,因为当前柱子的高度可能大于min(当前柱子左侧最高柱子高度,当前柱子右侧最高柱子高度),实际情况也就是无法形成一个接住水的区域,则我们将其设置为0。

解题方法

1.暴力法:一遍遍历,每次寻找当前柱子左、右侧的最高柱子,再将min(当前柱子左侧最高柱子高度,当前柱子右侧最高柱子高度) - 当前柱子高度加到结果上(注意若其结果为正则直接加,为负置为0)
2.前缀和:先通过遍历每次记录当前柱子及其左侧的最高值当前柱子及其右侧柱子的最高值,再将min(当前柱子及其左侧的最高值,当前柱子及其右侧柱子的最高值)-当前柱子的高度值加到结果上(注意此时由于在记录当前柱子及其左侧的最高值当前柱子及其右侧柱子的最高值的操作中已经记录了当前柱子的高度值,则最后再不用判断每次要加到结果上的值是否小于0)

复杂度

  • 时间复杂度:

暴力法: O ( n 2 ) O(n^2) O(n2)
前缀和: O ( n ) O(n) O(n)

  • 空间复杂度:

暴力法: O ( 1 ) O(1) O(1)
前缀和: O ( n ) O(n) O(n)

Code

class Solution {//暴力法//Time Complexity: O(N^2)//Space Complexity: O()public int trap(int[] height) {int res = 0;//从第2()个柱子开始到倒数第二个for (int i = 1; i < height.length - 1; ++i) {//寻找当前左侧最高柱子int leftMax = 0;for (int j = 0; j < i; ++j) {if (height[j] > leftMax) {leftMax = height[j];}}//寻找当前右侧最高柱子int rightMax = 0;for (int j = i + 1; j < height.length; ++j) {if (height[j] > rightMax) {rightMax = height[j];}}//当前柱子两侧最高柱子的较低值//减去当前柱子的长度即为当前储水量//如果carry小于0,则为0int carry = Math.min(rightMax,leftMax) - height[i];if (carry < 0) carry = 0;res += carry;}return res;}
}

class Solution {//前缀数组//Time Complexity: O(N)//Space Complexity: O(N)public int trap(int[] height) {int n = height.length;//前缀maxint[] leftMax = new int[n];int max = 0;for (int i = 0; i < n; ++i) {//寻找当前左边(包括本身)的最大值leftMax[i] = Math.max(max,height[i]);max = leftMax[i];}//后缀maxint[] rightMax = new int[n];max = 0;for (int i = n - 1; i >= 0; --i) {//寻找当前右边边(包括本身)的最大值rightMax[i] = Math.max(max,height[i]);max = rightMax[i];}//计算柱子之上接到的雨水int res = 0;for (int i = 1; i < n - 1; ++i) {res += Math.min(leftMax[i], rightMax[i]) - height[i];}return res;}
}

相关文章:

力扣42.接雨水(java,暴力法、前缀和解法)

Problem: 42. 接雨水 文章目录 思路解题方法复杂度Code 思路 要能接住雨水&#xff0c;感性的认知就是要形成一个“下凹区域”&#xff0c;则此时我们就要比较当前柱子和其左右柱子高度的关系&#xff0c;易得一个关键的式子&#xff1a;当前小区域的积水 min&#xff08;当前…...

hdlbits系列verilog解答(移位寄存器)-23

文章目录 一、问题描述二、verilog源码三、仿真结果 一、问题描述 您将获得一个具有两个输入和一个输出的模块 my_dff &#xff08;实现 D 触发器&#xff09;。实例化其中的三个&#xff0c;然后将它们链接在一起以形成长度为 3 的移位寄存器。端口 clk 需要连接到所有实例。…...

Linux命令记载

服务器基本操作 SSH登录服务器 ssh -p 端口号 用户名服务器IP 输入密码SFTP上传文件 #输入密码 #使用get命令下载远程服务器的文件&#xff0c;比如/usr/test.txt sftp>get /usr/test.txt#使用put命令上传本地文件到服务器&#xff0c;比如/usr/test1.txt sftp> put /…...

Flume 快速入门【概述、安装、拦截器】

文章目录 什么是 Flume&#xff1f;Flume 组成Flume 安装Flume 配置任务文件应用示例启动 Flume 采集任务 Flume 拦截器编写 Flume 拦截器拦截器应用 什么是 Flume&#xff1f; Flume 是一个开源的数据采集工具&#xff0c;最初由 Apache 软件基金会开发和维护。它的主要目的是…...

【pandas技巧】group by+agg+transform函数

目录 1. group by单个字段单个聚合 2. group by单个字段多个聚合 3. group by多个字段单个聚合 4. group by多个字段多个聚合 5. transform函数 studentsgradesexscoremoney0小狗小学部female958441小猫小学部male938362小鸭初中部male838543小兔小学部female909314小花小…...

一文解读WordPress网站的各类缓存-老白博客

缓存是一种重要的WordPress优化手段&#xff0c;用于提高网站的性能和加载速度。减少计算量&#xff0c;有效提升响应速度&#xff0c;让有限的资源服务更多的用户。本文老白博客便从自己的使用简单给大家介绍下WordPress的缓存&#xff0c;包括 站点缓存&#xff08;Page Cach…...

从零开始:开发直播商城APP的技术指南

时下&#xff0c;直播商城APP已经成了线上购物、电子商务的核心组成&#xff0c;本文将为您提供一个全面的技术指南&#xff0c;帮助您从零开始开发一个直播商城APP。我们将涵盖所有关键方面&#xff0c;包括技术堆栈、功能模块、用户体验和安全性。 第一部分&#xff1a;技术…...

GZ035 5G组网与运维赛题第6套

2023年全国职业院校技能大赛 GZ035 5G组网与运维赛项&#xff08;高职组&#xff09; 赛题第6套 一、竞赛须知 1.竞赛内容分布 竞赛模块1--5G公共网络规划部署与开通&#xff08;35分&#xff09; 子任务1&#xff1a;5G公共网络部署与调试&#xff08;15分&#xff09; …...

分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测(自注意力机制)

分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测&#xff08;自注意力机制&#xff09; 目录 分类预测 | Matlab实现KOA-CNN-GRU-selfAttention多特征分类预测&#xff08;自注意力机制&#xff09;分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matla…...

【Qt】QString怎么转成int

2023年10月29日&#xff0c;周日晚上 第一种方法 这种方法会尝试将 QString 对象转换为 int 类型。如果转换成功&#xff0c;将返回转换后的 int 值&#xff1b;如果转换失败&#xff08;例如&#xff0c;字符串中包含非数字字符&#xff09;&#xff0c;则返回 0。 QString…...

ubuntu 22.04 安装python-pcl

ubuntu 22.04 安装python-pcl 安装python-pcl修复bug 由于python-pcl库基本已经停止维护&#xff0c;所以Ubuntu22.04 在使用pip install python-pcl安装的时候会出现版本不适配的原因 安装python-pcl 使用Ubuntu22系统自带python3安装python-pcl&#xff0c;随后将下载的包拷…...

【题解】[GenshinOI Round 3 ]P9817 lmxcslD

题目传送门 分析 看到这道题我一开始是有点懵的&#xff0c;但是看了看数据范围&#xff0c;发现有几个点有 n 为质数 的特殊性质&#xff0c;结论先行&#xff0c;大胆猜测是不是可以贪心&#xff0c;所以先打了一个最傻的代码上去试试. void solve(){cin >> n >&…...

在pycharm中,远程操作服务器上的jupyter notebook

一、使用场景 现在我们有两台电脑&#xff0c;一台是拥有高算力的服务器&#xff0c;另一台是普通的轻薄笔记本电脑。如何在服务器上运行jupyter notebook&#xff0c;同时映射到笔记本电脑上的pycharm客户端中进行操作呢&#xff1f; 二、软件 pycharm专业版&#xff0c;jupy…...

SQL 运算符

SQL 运算符 运算符是保留字或主要用于 SQL 语句的 WHERE 子句中的字符&#xff0c;用于执行操作&#xff0c;例如&#xff1a;比较和算术运算。 这些运算符用于指定 SQL 语句中的条件&#xff0c;并用作语句中多个条件的连词。 常见运算符有以下几种&#xff1a; 算术运算符比…...

中间件安全-CVE 复现K8sDockerJettyWebsphere漏洞复现

目录 服务攻防-中间件安全&CVE 复现&K8s&Docker&Jetty&Websphere中间件-K8s中间件-Jetty漏洞复现CVE-2021-28164-路径信息泄露漏洞CVE-2021-28169双重解码信息泄露漏洞CVE-2021-34429路径信息泄露漏洞 中间件-Docker漏洞复现守护程序 API 未经授权访问漏洞…...

系列九、什么是Spring bean

一、什么是Spring bean 一句话&#xff0c;被Spring容器管理的bean就是Spring bean。...

轻量封装WebGPU渲染系统示例<4>-CubeMap/天空盒(源码)

当前示例源码github地址: https://github.com/vilyLei/voxwebgpu/blob/version-1.01/src/voxgpu/sample/ImgCubeMap.ts 此示例渲染系统实现的特性: 1. 用户态与系统态隔离。 2. 高频调用与低频调用隔离。 3. 面向用户的易用性封装。 4. 渲染数据和渲染机制分离。 5. 用户…...

Linux 环境变量 二

目录 获取环境变量的后两种方法 环境变量具有全局属性 内建命令 和环境变量相关的命令 c语言访问地址 重新理解地址 地址空间 获取环境变量的后两种方法 main函数的第三个参数 &#xff1a;char* env[ ] 也是一个指针数组&#xff0c;我们可以把它的内容打印出来看看。 …...

Beyond Compare4 30天试用到期的解决办法

相信很多小伙伴都有在使用Beyond Compare 4软件&#xff0c;如果我们没有激活该软件&#xff0c;就只有30天的评估使用期&#xff0c;那么过了这30天后我们怎么继续使用呢&#xff1f;下面小编就来为大家介绍方法。 打开Beyond Compare4&#xff0c;提示已经超出30天试用期限制…...

sentinel规则持久化-规则同步nacos-最标准配置

官方参考文档&#xff1a; 动态规则扩展 alibaba/Sentinel Wiki GitHub 需要修改的代码如下&#xff1a; 为了便于后续版本集成nacos&#xff0c;简单讲一下集成思路 1.更改pom 修改sentinel-datasource-nacos的范围 将 <dependency><groupId>com.alibaba.c…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...