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

代码随想录训练营第六十三天打卡|503.下一个更大元素II 42. 接雨水

503.下一个更大元素II

1.暴力法,和每日温度那一题如出一辙,循环数组用了一个取模运算就解决了。

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int> result;for (int i = 0; i < n; i++) {int j;for (j = 1; j < n; j++) {if (nums[(i + j) % n] > nums[i]) {break;}}if (j == n)result.push_back(-1);elseresult.push_back(nums[(i + j) % n]);}return result;}
};

2.单调栈法。相比于之前的单调栈,多了循环数组的处理,很高兴一下子就想到了最简洁的写法。

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();stack<int> st;vector<int> result(n, -1);for (int i = 0; i < n * 2; i++) {while (!st.empty() && nums[i % n] > nums[st.top()]) {result[st.top()] = nums[i % n];st.pop();}st.push(i % n);}return result;}
};

42. 接雨水

知名hard题,自己想挑战一下,缝缝补补写了一个多小时依然只能通过四分之一左右的测试用例,遂放弃。

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) {stack<int> st;int sum = 0;for (int i = 0; i < height.size(); i++) {while (!st.empty() && height[i] > height[st.top()]) {int mid = st.top();st.pop();if (!st.empty()) {int h = min(height[i], height[st.top()]) - height[mid];int w = i - st.top() - 1;sum += h * w;}}st.push(i);}return sum;}
};

3.单调栈。(注释版)理解了逻辑,代码并不复杂。

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;}
};

今日总结:接雨水。

相关文章:

代码随想录训练营第六十三天打卡|503.下一个更大元素II 42. 接雨水

503.下一个更大元素II 1.暴力法&#xff0c;和每日温度那一题如出一辙&#xff0c;循环数组用了一个取模运算就解决了。 class Solution { public:vector<int> nextGreaterElements(vector<int>& nums) {int n nums.size();vector<int> result;for (i…...

【web】nginx+php环境搭建-关键点(简版)

一、nginx和php常用命令 命令功能Nginxphp-fpm启动systemctl start nginxsystemctl start php-fpm停止systemctl stop nginxsystemctl stop php-fpm重启systemctl restart nginxsystemctl restart php-fpm查看启动状态systemctl status nginxsystemctl status php-fpm开机自启…...

1、什么是ETF?

ETF是Exchange Traded Fund的英文缩写&#xff0c;中文称为“交易型开放式指数基金”&#xff0c;又称“指数股”。ETF是一种指数投资工具&#xff0c;通过复制标的指数来构建跟踪指数变化的组合证券&#xff0c;使得投资者通过买卖一种产品就实现了一揽子证券的交易。简单来说…...

备战蓝桥杯Day18 - 双链表

一、每日一题 蓝桥杯真题之工作时长 这个题写代码做的话很麻烦&#xff0c;而且我也不一定能写出来&#xff0c;所以我直接就是用的excel来计算的时间和。 使用excel的做法 1.先把文件中的时间复制到excel中。 2.把日期和时间分到两列。 分成两列的步骤&#xff1a; 选中要…...

【大数据】Flink 内存管理(二):JobManager 内存分配(含实际计算案例)

《Flink 内存管理》系列&#xff08;已完结&#xff09;&#xff0c;共包含以下 4 篇文章&#xff1a; Flink 内存管理&#xff08;一&#xff09;&#xff1a;设置 Flink 进程内存Flink 内存管理&#xff08;二&#xff09;&#xff1a;JobManager 内存分配&#xff08;含实际…...

(2024,Sora 逆向工程,DiT,LVM 技术综述)Sora:大视觉模型的背景、技术、局限性和机遇回顾

Sora: A Review on Background, Technology, Limitations, and Opportunities of Large Vision Models 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 1. 简介 2. 背景 2.1…...

MySQL基础(二)

文章目录 MySQL基础&#xff08;二&#xff09;1. 数据库操作-DQL1.1 介绍1.2 语法1.3 基本查询1.4 条件查询1.5 聚合函数1.6 分组查询1.7 排序查询1.8 分页查询1.9 案例1.9.1 案例一1.9.2 案例二 2. 多表设计2.1 一对多2.1.1 表设计2.1.2 外键约束 2.2 一对一2.3 多对多2.4 案…...

el-table 多选表格存在分页,编辑再次操作勾选会丢失原来选中的数据

el-table表格多选时&#xff0c;只需要添加type"selection"&#xff0c; row-key及selection-change&#xff0c;如果存在分页时需要加上reserve-selection&#xff0c;这里就不写具体的实现方法了&#xff0c;可以查看我之前的文章&#xff0c;这篇文章主要说一下存…...

备战蓝桥杯————如何判断回文链表

如何判断回文链表 题目描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&#xff1a;…...

linux 文本编辑命令【重点】

目录 vi&vim介绍 vim安装 vim使用 查找命令 find grep 文本编辑的命令&#xff0c;主要包含两个: vi 和 vim vi&vim介绍 作用: vi命令是Linux系统提供的一个文本编辑工具&#xff0c;可以对文件内容进行编辑&#xff0c;类似于Windows中的记事本 语法: vi file…...

C#面:ref 和 out 的区别

ref 关键字&#xff1a; 在使用 ref 关键字时&#xff0c;传递的参数必须在方法调用之前进行初始化。在方法内部&#xff0c;对 ref 参数的任何修改都会影响到原始变量。ref 参数在方法内部和外部都必须具有相同的类型。 out 关键字 out 参数在方法内部必须被赋值。在使用 ou…...

php脚本输出中文在浏览器中显示乱码

问题说明 这个问题一般出现在较低版本的php中&#xff0c;原因是php和浏览器的字符解析方式不对应 &#xff0c;导致中文字符被错误解析成乱码 &#xff08;注&#xff0c;此处的php版本任意切换是依赖于小皮面板&#xff08;phpstudy&#xff09;实现的&#xff0c;感兴趣可以…...

【Unity每日一记】角色控制器Character Contorller

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…...

Kafka入门介绍一

介绍 Kafka是一个分布式系统&#xff0c;由服务器和客户端组成&#xff0c;通过高性能TCP网络协议进行通信。它可以部署在本地和云中的裸机硬件、虚拟机和容器上环境。 服务器&#xff1a;Kafka作为一个或多个服务器的群集运行&#xff0c;这些服务器可以跨越多个数据中心或云…...

leetcode 3.反转链表;

1.题目&#xff1a; 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 2.用例&#xff1a; 3.题目解析&#xff1a; &#xff08;1&#xff09;函数头&#xff1a; 要求返回结点&#xff0c;就 ListNode* reverseList(ListNode* head)&…...

【蓝桥杯】快读|min和max值的设置|小明和完美序列|​顺子日期​|星期计算|山

目录 一、输入的三种方式 1.最常见的Scanner的输入方法 2.数据多的时候常用BufferedReader快读 3.较麻烦的StreamTokenizer快读&#xff08;用的不多&#xff09; StreamTokenizer常见错误&#xff1a; 二、min和max值的设置 三、妮妮的翻转游戏 四、小明和完美序列 五…...

半小时到秒级,京东零售定时任务优化怎么做的?

导言&#xff1a; 京东零售技术团队通过真实线上案例总结了针对海量数据批处理任务的一些通用优化方法&#xff0c;除了供大家借鉴参考之外&#xff0c;也更希望通过这篇文章呼吁大家在平时开发程序时能够更加注意程序的性能和所消耗的资源&#xff0c;避免在流量突增时给系统…...

stm32——hal库学习笔记(ADC)

这里写目录标题 一、ADC简介&#xff08;了解&#xff09;1.1&#xff0c;什么是ADC&#xff1f;1.2&#xff0c;常见的ADC类型1.3&#xff0c;并联比较型工作示意图1.4&#xff0c;逐次逼近型工作示意图1.5&#xff0c;ADC的特性参数1.6&#xff0c;STM32各系列ADC的主要特性 …...

一周学会Django5 Python Web开发-Http请求HttpRequest请求类

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计25条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…...

element el-date-picker 日期组件置灰指定日期范围、禁止日期范围日期选择

JS如何将当前日期或指定日期转时间戳_javascript技巧_脚本之家 小于指定日期前的日期置灰 比如这里 指定日期是 2024-02-20 10:48:15 disabledDate(time) time是一个函数提供的时间用于比较 他是一个时间戳↓ 理解为我们想要置灰的时间 time.getTime() < timeStamps- 1 *…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

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

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

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

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;用于图像分割或平滑处理。 该函数将输入图像中的…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...