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

代码随想录算法训练营 day59|503.下一个更大元素II、42. 接雨水

一、503.下一个更大元素II

力扣题目链接

可以不扩充nums,在遍历的过程中模拟走两边nums

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);if (nums.size() == 0) return result;stack<int> st;st.push(0);for (int i = 1; i < nums.size() * 2; i++) { // 模拟遍历两边nums,注意一下都是用i % nums.size()来操作if (nums[i % nums.size()] < nums[st.top()]) st.push(i % nums.size());else if (nums[i % nums.size()] == nums[st.top()]) st.push(i % nums.size()); else {while (!st.empty() && nums[i % nums.size()] > nums[st.top()]) {result[st.top()] = nums[i % nums.size()];st.pop();}st.push(i % nums.size());}}return result;}
};

二、42. 接雨水

力扣题目链接

1)双指针法

把每一个位置的左边最高高度记录在一个数组上(maxLeft),右边最高高度记录在一个数组上(maxRight),避免了重复计算。

当前位置,左边的最高高度是前一个位置的左边最高高度和本高度的最大值。

即从左向右遍历:maxLeft[i] = max(height[i], maxLeft[i - 1]);

从右向左遍历:maxRight[i] = max(height[i], maxRight[i + 1]);

class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0;vector<int> maxLeft(height.size(), 0);vector<int> maxRight(height.size(), 0);int size = maxRight.size();// 记录每个柱子左边柱子最大高度maxLeft[0] = height[0];for (int i = 1; i < size; i++) {maxLeft[i] = max(height[i], maxLeft[i - 1]);}// 记录每个柱子右边柱子最大高度maxRight[size - 1] = height[size - 1];for (int i = size - 2; i >= 0; i--) {maxRight[i] = max(height[i], maxRight[i + 1]);}// 求和int sum = 0;for (int i = 0; i < size; i++) {int count = min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}
};

2)单调栈解法 

class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0; // 可以不加stack<int> st; // 存着下标,计算的时候用下标对应的柱子高度st.push(0);int sum = 0;for (int i = 1; i < height.size(); i++) {if (height[i] < height[st.top()]) {     // 情况一st.push(i);} if (height[i] == height[st.top()]) {  // 情况二st.pop(); // 其实这一句可以不加,效果是一样的,但处理相同的情况的思路却变了。st.push(i);} else {                                // 情况三while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是whileint mid = st.top();st.pop();if (!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1; // 注意减一,只求中间宽度sum += h * w;}}st.push(i);}}return sum;}
};

 

相关文章:

代码随想录算法训练营 day59|503.下一个更大元素II、42. 接雨水

一、503.下一个更大元素II 力扣题目链接 可以不扩充nums&#xff0c;在遍历的过程中模拟走两边nums class Solution { public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);if (nums.size() 0) return…...

MyBatis数据库操作

文章目录 前言一、MyBatis的各种查询功能1.查询一个实体类对象2.查询一个List集合3.查询单个数据4.查询一条数据为map集合5.查询多条数据为map集合方法一方法二 6.测试类 二、特殊SQL的执行1.模糊查询2.批量删除3.动态设置表名5.添加功能获取自增的主键6.测试类 三、自定义映射…...

python flask框架 debug功能

从今天开始&#xff0c;准备整理一些基础知识&#xff0c;分享给需要的人吧 先整理个flask的debug功能&#xff0c;首先列举一下debug加与不加的区别&#xff0c;然后再上代码和图看看差异 区别&#xff1a; &#xff08;1&#xff09;加了debug后&#xff0c;修改js&#xf…...

《深入浅出OCR》第六章:OCR数据集与评价指标

一、OCR技术流程 在介绍OCR数据集开始&#xff0c;我将带领大家和回顾下OCR技术流程&#xff0c;典型的OCR技术pipline如下图所示&#xff0c;其中&#xff0c;文本检测和识别是OCR技术的两个重要核心技术。 1.1 图像预处理&#xff1a; 图像预处理是OCR流程的第一步&#xf…...

15. 线性代数 - 克拉默法则

文章目录 克拉默法则矩阵运算Hi,大家好。我是茶桁。 上节课我们在最后提到了一个概念「克拉默法则」,本节课,我们就来看看到底什么是克拉默法则。 克拉默法则 之前的课程我们一直在强调,矩阵是线性方程组抽象的来的。那么既然我们抽象出来了,有没有一种比较好的办法高效…...

【LeetCode】剑指 Offer <二刷>(6)

目录 题目&#xff1a;剑指 Offer 12. 矩阵中的路径 - 力扣&#xff08;LeetCode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;剑指 Offer 13. 机器人的运动范围 - 力扣&#…...

jsp页面出现“String cannot be resolved to a type”错误解决办法

篇首语&#xff1a;小编为大家整理&#xff0c;主要介绍了jsp页面出现“String cannot be resolved to a type”错误解决办法相关的知识&#xff0c;希望对你有一定的参考价值。 jsp页面出现“String cannot be resolved to a type”错误解决办法 解决办法&#xff1a; 右键项目…...

【go-zero】使用自带Redis方法

yaml配置文件 RedisS:Host: Type: Pass: config增加 RedisS struct {Host stringType stringPass string}svc文件 type * struct {RedisClient *redis.Redis } func *(c config.Config) * {sqlConn : sqlx.NewMysql(c.DB.DataSource)return &*{RedisClient: redis.New(c…...

离线数仓同步数据3

业务数据_增量表数据同步 1&#xff09;Flume配置概述2&#xff09;Flume配置实操3&#xff09;通道测试4&#xff09;编写Flume启停脚本 1&#xff09;Flume配置概述 Flume需要将Kafka中topic_db主题的数据传输到HDFS&#xff0c;故其需选用KafkaSource以及HDFSSink&#xff…...

Prometheus+Grafana 搭建应用监控系统

一、背景 完善的监控系统可以提高应用的可用性和可靠性&#xff0c;在提供更优质服务的前提下&#xff0c;降低运维的投入和工作量&#xff0c;为用户带来更多的商业利益和客户体验。下面就带大家彻底搞懂监控系统&#xff0c;使用Prometheus Grafana搭建完整的应用监控系统。 …...

Spring Boot整合Log4j2.xml的问题

文章目录 问题解决参考 问题 Spring Boot整合Log4j2.xml的时候返回以下错误&#xff1a; Caused by: org.apache.logging.log4j.LoggingException: log4j-slf4j-impl cannot be present with log4j-to-slf4j 进行了解决。 解决 Spring Boot整合Log4j2.xml经过以下操作&#…...

代码随想录算法训练营第五十八天 | 739. 每日温度,496.下一个更大元素 I

代码随想录算法训练营第五十八天 | 739. 每日温度&#xff0c;496.下一个更大元素 I 739. 每日温度496.下一个更大元素 I 739. 每日温度 题目链接 视频讲解 给定一个整数数组 temperatures &#xff0c;表示每天的温度&#xff0c;返回一个数组 answer &#xff0c;其中 answe…...

【动手学深度学习】--文本预处理

文章目录 文本预处理1.读取数据集2.词元化3.词表4.整合所有功能 文本预处理 学习视频&#xff1a;文本预处理【动手学深度学习v2】 官方笔记&#xff1a;文本预处理 对于序列数据处理问题&#xff0c;在【序列模型】中评估了所需的统计工具和预测时面临的挑战&#xff0c;这…...

2023年最佳研发管理平台评选:哪家表现出色?

“研发管理平台哪家好&#xff1f;以下是一些知名的研发管理软件品牌&#xff1a;Zoho Projects、JIRA、Trello、Microsoft Teams、GitLab。’” 企业需要不断创新以保持竞争力。研发是企业创新的核心&#xff0c;而研发管理平台则为企业提供了一个有效的工具来支持和管理其研发…...

轻量容器引擎Docker基础使用

轻量容器引擎Docker Docker是什么 Docker 是一个开源项目&#xff0c;诞生于 2013 年初&#xff0c;最初是 dotCloud 公司内部的一个业余项目。 它基于 Google 公司推出的 Go 语言实现&#xff0c;项目后来加入了 Linux 基金会&#xff0c;遵从了 Apache 2.0 协议&#xff0c;…...

questions

1.JDK 和 JRE 有什么区别&#xff1f; JDK&#xff1a;Java Development Kit 的简称&#xff0c;java 开发工具包&#xff0c;提供了 java 的开发环境和运行环境 JRE&#xff1a;Java Runtime Environment 的简称&#xff0c;java 运行环境&#xff0c;为 java 的运行提供了所需…...

MojoTween:使用「Burst、Jobs、Collections、Mathematics」优化实现的Unity顶级「Tween动画引擎」

MojoTween是一个令人惊叹的Tween动画引擎&#xff0c;针对C#和Unity进行了高度优化&#xff0c;使用了Burst、Jobs、Collections、Mathematics等新技术编码。 MojoTween提供了一套完整的解决方案&#xff0c;将Tween动画应用于Unity Objects的各个方面&#xff0c;并可以通过E…...

Vue3响应式源码实现

Vue3响应式源码实现 初始化项目结构 vue-proxy ├── effect.js ├── effect.ts ├── index.html ├── index.js ├── package.json ├── reactive.js ├── reactive.ts └── webpack.config.jsreactive.ts import { track, trigger } from "./effect&q…...

【RapidAI】P1 中文文本切割程序

中文文本切割程序 基本信息代码解析相关包获取 yaml 关键文件类的构造函数切分语句部分特殊处理 PDF重点切分去除数组中空字符串再度切分后长度 附录附录一&#xff1a;完整代码附录二&#xff1a;可继续思考问题 基本信息 文件名&#xff1a; chinese_text_splitter.py 文件地…...

4、QT中的网络编程

一、Linux中的网络编程 1、子网和公网的概念 子网网络&#xff1a;局域网&#xff0c;只能进行内网的通信公网网络&#xff1a;因特网&#xff0c;服务器等可以进行远程的通信 2、网络分层模型 4层模型&#xff1a;应用层、传输层、网络层、物理层 应用层&#xff1a;用户自…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

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

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