代码随想录第39天:单调栈
一、每日温度(Leetcode 739)
思路:
-
栈里存放的是**“还没等到升温的日子”**的索引;
-
每遇到一个新的温度:
-
检查是否比栈顶的温度高;
-
如果高了,说明升温来了,栈顶元素可以出栈,并计算等待天数;
-
-
一旦栈为空或当前温度不高于栈顶,就入栈。
class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)res = [0] * n # 初始化结果数组stack = [] # 存放的是索引,栈中温度递减for i in range(n):# 如果当前温度高于栈顶(之前某一天)的温度while stack and temperatures[i] > temperatures[stack[-1]]:prev_index = stack.pop()res[prev_index] = i - prev_index # 计算天数差stack.append(i) # 当前索引入栈return res
二、下一个更大元素 I(Leetcode 496)
思路:
-
用单调栈求出
nums2
中每个元素右边第一个更大的数。 -
用字典
greater_map
存储这个映射关系:{元素: 它右边第一个更大的元素}
。 -
最后,对
nums1
中的每个数,从字典中查找答案,不存在则返回-1
。
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:stack = []greater_map = {}for num in nums2:# 栈中元素递减,当前元素比栈顶大 -> 出栈并记录while stack and num > stack[-1]:prev = stack.pop()greater_map[prev] = numstack.append(num)# 栈中剩下的元素右边没有更大值,默认是 -1return [greater_map.get(x, -1) for x in nums1]
三、下一个更大元素 II (Leetcode 503)
思路:
我们可以将数组遍历两遍(通过 %
模拟循环),来处理尾部比头部大的情况:
-
用
i % n
实现数组循环; -
只在第一轮把索引入栈,防止重复处理;
-
第二轮仅用来帮助“解决前面的元素右边没人比它大的问题”。
class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)res = [-1] * n # 初始化结果为 -1stack = []# 遍历两轮数组for i in range(2 * n):num = nums[i % n]while stack and nums[stack[-1]] < num:index = stack.pop()res[index] = numif i < n:stack.append(i) # 只在第一轮入栈return res
四、接雨水(Leetcode 42)
1.动态规划:
-
当前格子能接多少水」取决于它左边和右边的最大高度中的较小值。
-
预先记录每个位置左侧和右侧最大高度
-
再计算每个位置能接多少水
class Solution:def trap(self, height: List[int]) -> int:n = len(height)if n == 0:return 0 # 边界处理:空数组无法存水# 初始化左右最大高度数组left_max = [0] * nright_max = [0] * n# 计算每个位置左边(包括自己)最高的柱子高度left_max[0] = height[0]for i in range(1, n):# 当前左最大高度 = 前一个位置的左最大高度 或 当前高度,取较大者left_max[i] = max(left_max[i - 1], height[i])# 计算每个位置右边(包括自己)最高的柱子高度right_max[-1] = height[-1]for i in range(n - 2, -1, -1):# 当前右最大高度 = 后一个位置的右最大高度 或 当前高度,取较大者right_max[i] = max(right_max[i + 1], height[i])# 遍历每个位置,计算该位置可接的水量res = 0for i in range(n):# 当前柱子最多能接的水 = 左右最大高度的较小值 - 当前高度# 如果左右最大高度都大于当前高度,才有水;否则为0res += min(left_max[i], right_max[i]) - height[i]return res # 返回总的接水量
2.单调栈:
-
遇到比栈顶高的柱子,说明可以接水,弹出栈顶,计算面积。
-
左边界:栈顶弹出后的新栈顶
-
右边界:当前元素
-
宽度 =
右边 - 左边 - 1
,高度 =min(height[left], height[right]) - height[中间]
class Solution:def trap(self, height: List[int]) -> int:stack = [] # 单调递减栈,存的是柱子的索引res = 0 # 累加接的水量for i, h in enumerate(height): # 遍历每个位置的柱子高度,i 是当前柱子的索引# 当前高度 h 比栈顶柱子高,说明可以形成“凹槽”接水while stack and h > height[stack[-1]]:bottom = stack.pop() # 凹槽的底部索引if not stack:break # 栈空了说明左边没墙,不能接水left = stack[-1] # 左边高墙的索引width = i - left - 1 # 宽度 = 当前右墙索引 i - 左墙索引 left - 1bounded_height = min(height[left], h) - height[bottom] # 高度 = 两边较矮墙 - 底部高度res += width * bounded_height # 当前“凹槽”能装的水stack.append(i) # 当前柱子索引入栈,可能成为新的“左墙”或“底部”return res
3.双指针:
-
左右指针从两端向中间移动。
-
维护两个变量:
left_max
和right_max
,分别表示左侧和右侧最高的墙。 -
某位置的接水量取决于
min(left_max, right_max) - height[i]
。
class Solution:def trap(self, height: List[int]) -> int:if not height:return 0 # 空数组无法接水,直接返回0left, right = 0, len(height) - 1 # 左右指针left_max, right_max = 0, 0 # 记录左右两侧最大高度res = 0 # 存储总共接到的水量while left < right:# 谁小就移动谁,决定接水能力的是较矮一方if height[left] < height[right]:if height[left] >= left_max:left_max = height[left] # 更新左侧最大值else:res += left_max - height[left] # 当前柱子能接的水 = 左侧最大高度 - 当前高度left += 1 # 左指针右移else:if height[right] >= right_max:right_max = height[right] # 更新右侧最大值else:res += right_max - height[right] # 当前柱子能接的水 = 右侧最大高度 - 当前高度right -= 1 # 右指针左移return res
-
总是处理 较矮的一侧,因为它才是限制水位高度的关键。
-
不需要额外数组,只用两个指针与两个变量记录左右最大值,节省空间,时间复杂度
O(n)
,空间复杂度O(1)
。
五、柱状图中最大的矩形(Leetcode 84)
单调栈:
-
对每个柱子,找到左边第一个小于它的柱子
left[i]
-
找到右边第一个小于它的柱子
right[i]
-
宽度为
right[i] - left[i] - 1
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:n = len(heights)left = [0] * n # 记录每个柱子左边第一个比它矮的位置索引right = [n] * n # 记录每个柱子右边第一个比它矮的位置索引stack = []# 从左到右遍历,计算 left[i]for i in range(n):# 栈中维护单调递增的柱子索引while stack and heights[stack[-1]] >= heights[i]:stack.pop()# 如果栈为空,说明左边没有比当前柱子矮的了left[i] = stack[-1] if stack else -1stack.append(i)# 清空栈用于接下来的右边界计算stack.clear()# 从右到左遍历,计算 right[i]for i in range(n - 1, -1, -1):# 栈中维护单调递增的柱子索引while stack and heights[stack[-1]] >= heights[i]:stack.pop()# 如果栈为空,说明右边没有比当前柱子矮的了right[i] = stack[-1] if stack else nstack.append(i)max_area = 0for i in range(n):# 当前柱子能延展的宽度 = right[i] - left[i] - 1width = right[i] - left[i] - 1# 面积 = 高度 × 宽度max_area = max(max_area, width * heights[i])return max_area
相关文章:
代码随想录第39天:单调栈
一、每日温度(Leetcode 739) 思路: 栈里存放的是**“还没等到升温的日子”**的索引; 每遇到一个新的温度: 检查是否比栈顶的温度高; 如果高了,说明升温来了,栈顶元素可以出栈&…...
如何在vite构建的vue项目中从0到1配置postcss-pxtorem
1. 安装postcss-pxtorem和autoprefixer yarn add postcss-pxtorem autoprefixer2. 在vite.config.ts中写入 import { defineConfig } from "vite"; import vue from "vitejs/plugin-vue"; import postcssPxtorem from "postcss-pxtorem"; impo…...
基于51单片机的自动洗衣机衣料材质proteus仿真
地址:https://pan.baidu.com/s/13d2bJ6vKh8ZLuDBZnI0VGw 提取码:1234 仿真图: 芯片/模块的特点: AT89C52/AT89C51简介: AT89C51 是一款常用的 8 位单片机,由 Atmel 公司(现已被 Microchip 收…...
永久免费的小工具,内嵌微软接口
有时候我们制作短视频,需要为视频添加声音,但部分配音软件要收费。不过别担心,今天给大家推荐一款超实用的免费文字转语音软件,完全无需担忧费用问题! 01 软件介绍 这款软件就是Read Aloud,具有以下特点&a…...
C++漫步结构与平衡的殿堂:AVL树
文章目录 1.AVL树的概念2.AVL树的结构3.AVL树的插入4.AVL树的旋转4.1 左单旋4.2 右单旋4.3 右左双旋4.4 左右双旋 5.AVL树的删除6.AVL树的高度7.AVL树的平衡判断希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力! 二叉搜索树有其自身的缺陷…...
MIST:一键解锁 macOS 历史版本,旧系统安装不再难!
在 Mac 电脑的使用过程中,你是否遇到过这些困扰?为了运行一款经典设计软件,新系统却无法兼容;或是想给老旧 Mac 设备升级,却找不到适配的系统版本。而 App Store 里,旧版 macOS 安装包就像 “隐藏副本”&am…...
mac连接lniux服务器教学笔记
从你的检查结果看,容器内已经安装了 XFCE 桌面环境(xfce.desktop 和 xubuntu.desktop 的存在说明桌面环境已存在)。以下是针对 Docker 容器环境的远程桌面配置方案: 一、容器内快速配置远程桌面(XFCE VNC)…...
网站公安备案流程及审核时间
在中国,网站运营除了需要 ICP备案(工信部备案),还需完成 公安备案(公安机关互联网站安全备案)。以下是详细流程及审核时间说明: 一、公安备案流程 1. 备案对象 所有在中国境内运营的网站&#…...
python学生作业提交管理系统-在线作业提交系统
目录 技术栈介绍具体实现截图系统设计研究方法:设计步骤设计流程核心代码部分展示研究方法详细视频演示试验方案论文大纲源码获取/详细视频演示 技术栈介绍 Django-SpringBoot-php-Node.js-flask 本课题的研究方法和研究步骤基本合理,难度适中…...
从颜料混色到网络安全:DH算法的跨界智慧
一、颜料混色的秘密 想象一下,你和朋友各自有一罐私密的颜料,但你们想共同调出一种只有彼此知道的新颜色,而旁观者即使看到你们的操作也无法复现。奇怪的是,你们全程没有直接交换颜料,却能达成共识——这就是**迪菲-赫…...
初学者的AI智能体课程:构建AI智能体的十堂课
初学者的AI智能体课程:构建AI智能体的十堂课 在人工智能(AI)领域,AI智能体正在逐渐发挥其不容忽视的作用。自动化的智能体不仅仅在理论上广泛讨论,更加在实际应用中开辟了一片新的天地。那么如何动手开发属于自己的AI智能体呢?Microsoft提供的AI智能体入门课正是为此而设…...
数据结构 - 8( AVL 树和红黑树 10000 字详解 )
一:二叉搜索树 1.1 回顾二叉搜索树 我们在树的章节中学习了二叉搜索树的概念。二叉搜索树满足以下性质:如果它的左子树存在,则左子树所有节点的值均小于根节点的值;如果右子树存在,则右子树所有节点的值均大于根节点…...
Tcp 通信简单demo思路
Server 端 -------------------------- 初始化部分 ------------------------------- 1.创建监听套接字: 使用socket(协议家族,套接字的类型,0) 套接字类型有 SOCK_STREAM:表示面向连接的套接字(Tcp协议)&…...
Cesium 导航控件(指南针 + 缩放按钮),自定义放置位置
Cesium 导航控件(指南针 缩放按钮) Cesium 导航控件(指南针 缩放按钮)的功能实现,从技术角度来看,可以整理出一整套实现流程和技术结构。这套流程结合了以下几个核心技术点: 1、整体功能目标 …...
MySQL的索引和事务
目录 1、索引 1.1 查看索引 1.2 创建索引 1.3 删除索引 1.4 索引的实现 2、事务 1、索引 索引等同于目录,属于针对查询操作的一个优化手段,可以通过索引来加快查询的速度,避免针对表进行遍历。 主键、unique和外键都是会自动生成索引的…...
【Fifty Project - D25】
今日完成记录 TimePlan完成情况9:00 - 11:30大论文修改修改情况书小论文修改√16:00 - 17 :00Leetcode√ Leetcode 每日一题 到达最后一个房间的最小时间II:和昨天的每日一题大致一样,增加一个条件&…...
pip下载tmp不够
问题描述 今天遇到一个小问题,在用pip安装的时候提示 ERROR: Could not install packages due to an OSError: [Errno 28] No space left on device 但我们单位用于生产环境的机器磁盘都是基本是论TB的,怎么会不够呢? 原因分析:…...
一种机载扫描雷达实时超分辨成像方法——论文阅读
一种机载扫描雷达实时超分辨成像方法 1. 专利的研究目标与产业意义1.1 研究目标与实际问题1.2 产业意义2. 专利的创新方法:滑窗递归优化与实时更新2.1 核心模型与公式2.2 与传统方法对比优势3. 实验设计与验证3.1 仿真参数3.2 实验结果4. 未来研究方向与挑战4.1 学术挑战4.2 技…...
nginx 会话保持(cookie的配置)
nginx会话保持主要有以下几种实现方式。 1. ip_hash ip_hash使用源地址哈希算法,将同一客户端的请求总是发往同一个后端服务器,除非该服务器不可用。 ip_hash语法: upstream backend { ip_hash; server backend1.example.com; server backend2.example.com; …...
nginx 实现动静分离
环境 : 三个机器,准备一个nginx代理 两个http 分别处理动态和静态 知识点--expires expires功能说明---(为客户端配置缓存时间) nginx缓存的设置可以提高网站性能,对于网站的图片,尤其是新闻网站,图片一旦发布,改动的可能是非常小的,为了减小对服务器请求的压力,提高…...
k8s的pod挂载共享内存
k8s的pod挂载共享内存,限制不生效问题: 注:/dev/shm 是 Linux 系统中用于共享内存的特殊路径。通过将 emptyDir 的 medium 设置为 Memory,可以确保 /dev/shm 正确地挂载到一个基于内存的文件系统,从而实现高效的共享内…...
Java高频面试之并发编程-14
hello啊,各位观众姥爷们!!!本baby今天又来报道了!哈哈哈哈哈嗝🐶 面试官:指令重排有限制没有?happens-before 又是什么? 在并发编程中,指令重排(…...
Linux基础(最常用基本命令)
1.查看文件ls 1.1 格式 ls 选项 参数,如:ls -lah ~/ 1.2 选项设置: -l:list 以列表方式显示文件 -h:human-readable 以人类可读的方式显示文件大小(会将纯数字转换为kb,mb) -a:all 显示所有的…...
【Python 日期和时间】
Python 中处理日期和时间主要依赖 datetime 模块,结合 dateutil 和 pytz 等第三方库可实现更复杂的需求。以下是日期和时间处理的核心知识点: 一、基础模块 1. datetime 模块 核心类:datetime, date, time, timedelta安装依赖:p…...
C#简易Modbus从站仿真器
C#使用NModbus库,编写从站仿真器,支持Modbus TCP访问,支持多个从站地址和动态启用/停用从站(模拟离线),支持数据变化,可以很方便实现,最终效果如图所示。 项目采用.net framework 4.…...
FPGA图像处理(四)------ 图像裁剪
timescale 1ns / 1ps // // Description: 图像裁剪算法 // module image_crop(input wire clk,input wire reset,input wire [10:0] img_width,input wire [10:0] img_height,input wire [10:0] img_x_start,input wire [10:0] img_x_end,input wire [10:0] img_y_start,input…...
1.MySQL数据库初体验
1.1数据库简介 1.1.1使用数据库的必要性 使用数据库可以高效且条理分明地存储数据,使人们能够更加迅速、方便地管理数据。 数据库特点: a.可以结构化存储大量地数据信息,方便用户进行有效的检索 b.可以有效地保持数据信息的一致性、完整…...
量子密码的轻量级通信协议笔记
代码笔记 本文档提供了项目代码的详细说明,包括代码结构、关键算法实现和重要的代码片段。 代码结构 . ├── Makefile # 构建系统配置 ├── coap_client.c # CoAP客户端实现 ├── coap_server.c # CoAP服务端实现 ├─…...
探索 C++ 在行业应用与技术融合中的核心价值
引言 在科技飞速发展的今天,C 作为一门兼具高性能与灵活性的编程语言,正深度融入游戏开发、人工智能、区块链等多个关键领域。其高效的内存管理、底层控制能力以及对现代硬件架构的深度优化,使其成为复杂系统开发的首选语言。本文将深入探讨…...
雷赛伺服电机
ACM0经济 编码器17位: ACM1基本 编码器23位磁编, ACM2通用 编码器24位光电, 插头定义:...
word文档基本操作: 编辑页眉页脚和插入目录
文章目录 引言I 编辑页眉页脚II 插入目录III 知识扩展基于axure画架构图基于Knife4j导出接口文档基于PDManer导出数据库设计文档引言 背景: 信息安全认证需要准备相关文件用于审核 一般的开发设计包含总体设计、概要设计、详细设计、接口设计、数据库设计、部署结构设计、原型…...
数据结构(二)——线性表的链式表示和实现
一、单链表 1.单链表的定义 如图所示每个节点包含两个域:数据域和指针域。数据域存储数据元素,指针域存储下一个节点的地址,因此指针指向的类型也是节点类型。每个指针都指向下一个节点,都是朝一个方向的,这样的链表称为单向链表…...
HTML10:iframe内联框架
iframe内部框架 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>内联框架学习</title> </head> <body> <!--iframe内联框架 src:地址 width-height:高度宽度 --> <iframe…...
C++代码随想录刷题知识分享-----数组交集—LeetCode 349
1 题目描述 给定两个整型数组 nums1 和 nums2,请返回它们的交集。 交集中 每个元素必须是唯一的。输出结果的顺序可以任意。 示例输入输出说明1nums1 [1,2,2,1], nums2 [2,2][2]2 只出现一次2nums1 [4,9,5], nums2 [9,4,9,8,4][4,9] 或 [9,4]顺序不作要求…...
Wireshark基本使用
本文会对Wireshark做简单介绍,带大家熟悉一下Wireshark的界面,以及如何使用过滤器。 接着会带大家查看TCP五层模型下,带大家回顾各层首部的格式。 最后会演示 Wireshark 如何抓取三次握手和四次挥手包的过程。 目录 一.Wireshark简介 二…...
学习c语言的链表的概念、操作(另一篇链表的笔记在其他的栏目先看这个)
在学习Linux之间我们先插入一下链表的知识 学习链表(一种数据结构思想) 链表和数组的区别和实现: 链表(链表是个好东西) 链表概念(什么是链表)? 链表就是数据结构->数据的存储…...
快速上手Pytorch Lighting框架 | 深度学习入门
快速上手Pytorch Lighting框架 | 深度学习入门 前言参考官方文档 介绍快速上手基本流程常用接口LightningModule\_\_init\_\_ & setup()\*\_step()configure_callbacks()configure_optimizers()load_from_checkpoint Trainer常用参数 可选接口LoggersTensorBoard Logger Ca…...
ffmpeg多媒体(音视频)处理常用命令
概览 总结一些音视频常用的ffmpeg处理命令,会不断更新,涉及一些重要命令,各位读者也可在评论区不断更新,维护起来,希望可以帮助大家快速解决问题! 1、音频相关 1.1 音频信息查看 ffmpeg -i test.wav 该命…...
QT中的网络请求
一、主程序(main.cpp) #include <QCoreApplication> #include <QNetworkAccessManager> #include <QNetworkReply> #include <QNetworkRequest> #include <QUrlQuery> #include <QJsonDocument> #include <QJso…...
Nacos源码—6.Nacos升级gRPC分析二
大纲 1.Nacos 2.x版本的一些变化 2.客户端升级gRPC发起服务注册 3.服务端进行服务注册时的处理 4.客户端服务发现和服务端处理服务订阅的源码分析 4.客户端服务发现和服务端处理服务订阅的源码分析 (1)Nacos客户端进行服务发现的源码 (2)Nacos服务端处理服务订阅请求的源…...
如何选择自己喜欢的cms
选择内容管理系统cms what is cms1.whatcms.org2.IsItWP.com4.Wappalyzer5.https://builtwith.com/6.https://w3techs.com/7. https://www.netcraft.com/8.onewebtool.com如何在不使用 CMS 检测器的情况下手动检测 CMS 结论 在开始构建自己的数字足迹之前,大多数人会…...
前端面经 作用域和作用域链
含义:JS中变量生效的区域 分类:全局作用域 或者 局部作用域 局部作用域:函数作用域 和 块级作用域ES6 全局作用域:在代码中任何地方都生效 函数中定义函数中生效,函数结束失效 块级作用域 使用let或const 声明 作用域链:JS查…...
开启智能Kubernetes管理新时代:kubectl-ai让操作更简单!
在如今的科技世界中,Kubernetes 已经成为容器编排领域的标杆,几乎所有现代应用的基础设施都离不开它。然而,面对复杂的集群管理和日常运维,许多开发者常常感到无所适从。今天,我们将为大家介绍一款结合了人工智能的强大工具——kubectl-ai。它不仅能帮助开发者更加顺畅地与…...
STM32 ADC
目录 ADC简介 逐次逼近型ADC STM32 ADC框图 输入通道 转换模式 •单次转换,非扫描模式 •连续转换,非扫描模式 •单次转换,扫描模式 •连续转换,扫描模式 触发控制 数据对齐 转换时间 校准 硬件电路 A…...
nextjs站点地图sitemap添加
app/sitemap.xml/route.ts (主站点地图索引) sitemap.xml 为文件夹名称 route.ts代码如下: import { NextResponse } from next/server; import { url } from /config/navigation; export async function GET() {// const entries generateMonthlyEntries();con…...
TCP/IP和OSI对比
TCP/IP模型的实际特性 网络层(IP层) 仅提供无连接的不可靠服务:TCP/IP模型的网络层核心协议是IP(Internet Protocol),其设计是无连接且不可靠的。IP数据包独立传输,不保证顺序、不确认交…...
【hadoop】Hbase java api 案例
代码实现: HBaseConnection.java package com.peizheng.bigdata;import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.hbase.HBaseConfiguration; import org.apache.hadoop.hbase.client.Connection; import org.apache.hadoop.hbase.client…...
深入理解Spring缓存注解:@Cacheable与@CacheEvict
在现代应用程序开发中,缓存是提升系统性能的重要手段。Spring框架提供了一套简洁而强大的缓存抽象,其中Cacheable和CacheEvict是两个最常用的注解。本文将深入探讨这两个注解的工作原理、使用场景以及最佳实践。 1. Cacheable注解 基本概念 Cacheable…...
[git]如何关联本地分支和远程分支
主题 本文总结如何关联git本地分支和远程分支的相关知识点。 详情 查看本地分支 git branch 查看远程分支 git branch -r 查看所有分支(本地远程) git branch -a 查看本地分支及其关联的远程分支(如有) git branch -vv 关联本地分支到远程分支: git branch …...
Linux58 ssh服务配置 jumpserver 测试双网卡 为何不能ping通ip地址
判断为NAT模式网卡 能ping 通外网 ens34为仅主机模式网卡 [rootlocalhost network-scripts]# ip route show default default via 10.1.1.254 dev ens33 proto static metric 100 10.0.0.0/8 dev ens33 proto kernel scope link src 10.1.1.37 metric 100 11.0.0.0/8 dev…...