代码随想录训练营第六十三天打卡|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.暴力法,和每日温度那一题如出一辙,循环数组用了一个取模运算就解决了。 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的英文缩写,中文称为“交易型开放式指数基金”,又称“指数股”。ETF是一种指数投资工具,通过复制标的指数来构建跟踪指数变化的组合证券,使得投资者通过买卖一种产品就实现了一揽子证券的交易。简单来说…...
备战蓝桥杯Day18 - 双链表
一、每日一题 蓝桥杯真题之工作时长 这个题写代码做的话很麻烦,而且我也不一定能写出来,所以我直接就是用的excel来计算的时间和。 使用excel的做法 1.先把文件中的时间复制到excel中。 2.把日期和时间分到两列。 分成两列的步骤: 选中要…...
【大数据】Flink 内存管理(二):JobManager 内存分配(含实际计算案例)
《Flink 内存管理》系列(已完结),共包含以下 4 篇文章: Flink 内存管理(一):设置 Flink 进程内存Flink 内存管理(二):JobManager 内存分配(含实际…...
(2024,Sora 逆向工程,DiT,LVM 技术综述)Sora:大视觉模型的背景、技术、局限性和机遇回顾
Sora: A Review on Background, Technology, Limitations, and Opportunities of Large Vision Models 公和众和号:EDPJ(进 Q 交流群:922230617 或加 VX:CV_EDPJ 进 V 交流群) 目录 0. 摘要 1. 简介 2. 背景 2.1…...
MySQL基础(二)
文章目录 MySQL基础(二)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表格多选时,只需要添加type"selection", row-key及selection-change,如果存在分页时需要加上reserve-selection,这里就不写具体的实现方法了,可以查看我之前的文章,这篇文章主要说一下存…...
备战蓝桥杯————如何判断回文链表
如何判断回文链表 题目描述 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 示例 1: 输入:head [1,2,2,1] 输出:true示例 2:…...
linux 文本编辑命令【重点】
目录 vi&vim介绍 vim安装 vim使用 查找命令 find grep 文本编辑的命令,主要包含两个: vi 和 vim vi&vim介绍 作用: vi命令是Linux系统提供的一个文本编辑工具,可以对文件内容进行编辑,类似于Windows中的记事本 语法: vi file…...
C#面:ref 和 out 的区别
ref 关键字: 在使用 ref 关键字时,传递的参数必须在方法调用之前进行初始化。在方法内部,对 ref 参数的任何修改都会影响到原始变量。ref 参数在方法内部和外部都必须具有相同的类型。 out 关键字 out 参数在方法内部必须被赋值。在使用 ou…...
php脚本输出中文在浏览器中显示乱码
问题说明 这个问题一般出现在较低版本的php中,原因是php和浏览器的字符解析方式不对应 ,导致中文字符被错误解析成乱码 (注,此处的php版本任意切换是依赖于小皮面板(phpstudy)实现的,感兴趣可以…...
【Unity每日一记】角色控制器Character Contorller
👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏:Uni…...
Kafka入门介绍一
介绍 Kafka是一个分布式系统,由服务器和客户端组成,通过高性能TCP网络协议进行通信。它可以部署在本地和云中的裸机硬件、虚拟机和容器上环境。 服务器:Kafka作为一个或多个服务器的群集运行,这些服务器可以跨越多个数据中心或云…...
leetcode 3.反转链表;
1.题目: 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 2.用例: 3.题目解析: (1)函数头: 要求返回结点,就 ListNode* reverseList(ListNode* head)&…...
【蓝桥杯】快读|min和max值的设置|小明和完美序列|顺子日期|星期计算|山
目录 一、输入的三种方式 1.最常见的Scanner的输入方法 2.数据多的时候常用BufferedReader快读 3.较麻烦的StreamTokenizer快读(用的不多) StreamTokenizer常见错误: 二、min和max值的设置 三、妮妮的翻转游戏 四、小明和完美序列 五…...
半小时到秒级,京东零售定时任务优化怎么做的?
导言: 京东零售技术团队通过真实线上案例总结了针对海量数据批处理任务的一些通用优化方法,除了供大家借鉴参考之外,也更希望通过这篇文章呼吁大家在平时开发程序时能够更加注意程序的性能和所消耗的资源,避免在流量突增时给系统…...
stm32——hal库学习笔记(ADC)
这里写目录标题 一、ADC简介(了解)1.1,什么是ADC?1.2,常见的ADC类型1.3,并联比较型工作示意图1.4,逐次逼近型工作示意图1.5,ADC的特性参数1.6,STM32各系列ADC的主要特性 …...
一周学会Django5 Python Web开发-Http请求HttpRequest请求类
锋哥原创的Python Web开发 Django5视频教程: 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计25条视频,包括:2024版 Django5 Python we…...
element el-date-picker 日期组件置灰指定日期范围、禁止日期范围日期选择
JS如何将当前日期或指定日期转时间戳_javascript技巧_脚本之家 小于指定日期前的日期置灰 比如这里 指定日期是 2024-02-20 10:48:15 disabledDate(time) time是一个函数提供的时间用于比较 他是一个时间戳↓ 理解为我们想要置灰的时间 time.getTime() < timeStamps- 1 *…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)
目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 编辑编辑 UDP的特征 socke函数 bind函数 recvfrom函数(接收函数) sendto函数(发送函数) 五、网络编程之 UDP 用…...
