力扣(LeetCode)1172. 餐盘栈(C++)
优先队列
解题思路:根据题意模拟。用数组存储无限数量的栈。重在实现 p u s h push push 和 p o p pop pop 操作。
- 对于 p u s h push push 操作,需要知道当前从左往右第一个空栈的下标。分两类讨论:
①所有栈都是满的,那么我们创建一个新栈,新栈存 p u s h push push 进来的值,再将新栈加入数组尾部。
②已存在的某些栈未满,那么从左往右遍历数组,找到第一个未满的栈,第一个未满的栈存 p u s h push push 进来的值。
这样一来,我们发现每个 p u s h push push 的操作②的最坏平均时间复杂度 O ( n ) O(n) O(n) ,一共 n n n 个 p u s h push push ,总体时间复杂度 O ( n 2 ) O(n^2) O(n2),题目给出 p u s h push push 操作最多调用 2 × 1 0 5 2 \times 10 ^ 5 2×105 次,时间 O ( n 2 ) O(n^2) O(n2) 必然超时。
操作②既然是遍历,有一个直观的优化方法:用优先队列,小根堆存储未满栈的下标。这样以来,维护未满的栈的时间复杂度就是 O ( l o g n ) O(logn) O(logn),每次维护完毕,堆顶就是最小下标。总体时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),可以接受。
-
对于 p o p pop pop 操作,它等价于 p o p A t S t a c k popAtStack popAtStack 操作,将参数 i n d e x index index 设为数组最后位置。
-
对于 p o p A t S t a c k popAtStack popAtStack 操作,简单模拟即可。
提示:对于优先队列的维护,请思考边界。也可以看代码注释。
class DinnerPlates {
public:int capacity;vector<stack<int>> S;priority_queue<int, vector<int>, greater<int>> pq; // 维护未满栈的下标DinnerPlates(int capacity) {this->capacity = capacity;}void push(int val) {if (pq.size() && pq.top() >= S.size()) { // 清空越界下标pq = priority_queue<int, vector<int>, greater<int>>();}// while (pq.size() && pq.top() >= S.size()) pq.pop(); // 清空越界下标if (pq.empty()) { // 插入新栈stack<int> ts;ts.push(val);if (capacity > 1) pq.push(S.size());S.push_back(ts);} else { // 插入第一个未满栈int pos = pq.top();S[pos].push(val);if (S[pos].size() >= capacity) { // 插入后,栈满pq.pop(); // 下标弹栈}}}int pop() {return popAtStack(S.size() - 1);}int popAtStack(int index) {if (index >= S.size() || S[index].empty()) {return -1;} else {int ans = S[index].top();S[index].pop();if (S[index].size() == capacity - 1) pq.push(index);while (S.size() && S.back().empty()) S.pop_back();return ans;}}
};
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) : 一共 n n n 次操作,每个操作的时间复杂度 O ( l o g n ) O(logn) O(logn) ,时间瓶颈在于维护堆。总体时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度 O ( n ) O(n) O(n) : 优先队列、栈的最坏空间复杂度 O ( n ) O(n) O(n)
AC

致语
- 理解思路很重要
- 读者有问题请留言,清墨看到就会回复的。
相关文章:
力扣(LeetCode)1172. 餐盘栈(C++)
优先队列 解题思路:根据题意模拟。用数组存储无限数量的栈。重在实现 p u s h push push 和 p o p pop pop 操作。 对于 p u s h push push 操作,需要知道当前从左往右第一个空栈的下标。分两类讨论: ①所有栈都是满的,那么我…...
详细说一下DotNet Core 、DotNet5、DotNet6和DotNet7的简介和区别
.NET是一种用于构建多种应用的免费开源开发平台,可以使用多种语言,编辑器和库开发Web应用、Web API和微服务、云中的无服务器函数、云原生应用、移动应用、桌面应用、Windows WPF、Windows窗体、通用 Windows平台 (UWP)、游戏、物联网 (IoT)、机器学习、…...
基于MBD的控制系统建模与仿真软件工具集
随着新能源汽车和自动驾驶技术的快速发展,汽车电子电气架构的发展已成为汽车行业推陈出新的主要动力:车内电控系统变得越来越复杂、软件迭代周期越来越短,汽车电子软件开发和测试的质量与效率要求也越来越高。汽车电控系统的设计开发已然成为…...
QML动画分组(Grouped Animations)
通常使用的动画比一个属性的动画更加复杂。例如你想同时运行几个动画并把他们连接起来,或者在一个一个的运行,或者在两个动画之间执行一个脚本。动画分组提供了很好的帮助,作为命名建议可以叫做一组动画。有两种方法来分组:平行与…...
探索未来的数字人生:全景VR数字人
在数字化时代,人工智能和虚拟现实技术正日益成为我们生活中不可或缺的一部分。而全景VR数字人,则是这一时代的最新产品,吸引了越来越多的关注和研究。 一、什么是全景VR数字人? 全景VR数字人是一种通过虚拟现实技术创造的数字人形…...
计算机基础 -- 硬件篇
首先,经常提起得计算机硬件都有啥? CPU,内存条,影片,显卡,声卡,网卡,主板,机箱电源,键鼠,显示器,音响,摄像头等 本次介绍内容为台式机与笔记本电脑的内容混合.CPU CPU(中央处理器)包含了运算器和控制器.相当于计算机的"大脑",决定了运算速度的快慢.算是电脑"最…...
【高危】Apache Superset <2.1.0 认证绕过漏洞(POC)(CVE-2023-27524)
漏洞描述 Apache Superset 是一个开源的数据可视化和业务智能平台,可用于数据探索分析和数据可视化。 Apache Superset 受影响版本在使用默认的secret_key时,攻击者可通过默认的secret_key为任意用户生成有效的会话令牌,进而绕过验证造成信…...
vue3如果用setup写如何获取类似于vue2中的this
Vue 3 是一款用于构建用户界面的 JavaScript 框架。 在 Vue 3 中,SFC(Single File Component)的 API 风格发生了变化,新增了 setup 函数而废弃了之前版本的 options API。setup 函数被认为是 Vue 3 的精华所在,它可以让…...
关于 API接口的一些知识分享
一、安全性 API接口的安全性主要表现在: 1、 API接口的提供者是经过认证的,并且不会将自己的用户信息透露给第三方 2、 API接口不能被第三方窃取或篡改 3、 API接口是一个相对安全的 API,不会轻易地被第三方截获和破解 4、 API接口一般都…...
【ROS仿真实战】Gazebo仿真平台介绍及安装方法(一)
文章目录 前言一、Gazebo简介二、Gazebo仿真平台的基本概念三、Gazebo仿真平台的安装方法四、总结 前言 Gazebo仿真平台是一个广泛应用于机器人研发、测试和教育等领域的开源软件。它可以模拟机器人的运动、感知和控制等行为,并提供了丰富的物理引擎、传感器模拟和…...
Lychee图床 - 本地配置属于自己的相册管理系统并远程访问
文章目录 1.前言2. Lychee网站搭建2.1. Lychee下载和安装2.2 Lychee网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 图床作为图片集中存放的服务网站,可以看做是云存储的一部分,既可…...
VP记录:Codeforces Round 865 (Div. 2) A~C
传送门:CF 难受了,本来想写到D题的,但是D题是一道交互题,只能作罢,提前润了 A题:A. Ian Visits Mary 简单的数学题,发现只要控制矩阵的宽为1就不可能在途中经过格点,直接实现即可(具体看代码) #include <bits/stdc.h> using namespace std; typedef long long ll; #de…...
智能学习 | MATLAB实现PSO-SVM多输入单输出回归预测(粒子群算法优化支持向量机)
智能学习 | MATLAB实现PSO-SVM多输入单输出回归预测(粒子群算法优化支持向量机) 目录 智能学习 | MATLAB实现PSO-SVM多输入单输出回归预测(粒子群算法优化支持向量机)预测效果基本介绍模型原理程序设计参考资料预测效果 基本介绍 MATLAB实现PSO-SVM多输入单输出回归预测(粒…...
Java后端:html转pdf实战笔记
目录 1、htmltopdf有什么用? 2、什么是wkhtmltopdf 3、wkhtmltopdf 参数介绍 4、示例项目 5、预览效果 1、htmltopdf有什么用? htmltopdf 是一款基于wkhtmltopdf技术的html转pdf文档java类库,支持html转pdf和url转pdf。 2、什么是wkhtmltopdf…...
设计模式-适配器模式
适配器模式 文章目录 适配器模式1、什么是适配器模式2、为什么要用适配器模式2.1、封装有缺陷的接口设计2.2、统一多个类的接口设计2.3、替换依赖的外部系统2.4、兼容老版本接口2.5、适配不同格式的数据 3、如何使用适配器模式1、类适配器2、对象适配器 总结 1、什么是适配器模…...
一款支持全文检索、工作流审批、知识图谱的企事业知识库
一、项目介绍 一款全源码,可二开,可基于云部署、私有部署的企业级知识库云平台,一款让企业知识变为实打实的数字财富的系统,应用在需要进行文档整理、分类、归集、检索、分析的场景。 获取方式q:262086839 为什么建立知识库平台&…...
SAP MRP例外信息解释
SAP中MRP的例外信息,一共分为八类,下面是所有例外信息的解释 第一类: 69:BOM组件可能是递归的,即自己的子集中包括了自己。 02:订单创建日期在过去,可能是没有及时处理,这个建议表…...
广义的S变换
广义的S变换 S变换中窗函数是高斯函数 1 2 π σ e − 1 2 σ t 2 \frac{1}{{\sqrt {2\pi } \sigma }}{e^{ - \frac{1}{{2\sigma }}{t^2}}} 2π σ1e−2σ1t2,它的形状由方差 σ 1 f \sigma\frac{1}{f} σf1控制。许多研究表明,S变换中窗函数的…...
python异常及其捕获
文章目录 异常的捕获异常是可传递的 异常的捕获 1.为什么要捕获异常? 在可能发生异常的地方,进行捕获。当异常出现的时候,提供解决方式,而不是任由其导致程序无法运行。 2.捕获异常的语法? try: 可能要发生异常的语句 except 异常名 as 别…...
mysql实现存在则保存,不存在则更新
方式1 ON DUPLICATE KEY UPDATE 使用前提:表必须配置唯一键或者主键,且保存的字段中包含该键【重点】 原理: ON DUPLICATE KEY UPDATE如果配合主键,存在数据a,新插入b,如果主键不冲突,会保存b…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
