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

力扣(LeetCode)1172. 餐盘栈(C++)

优先队列

解题思路:根据题意模拟。用数组存储无限数量的栈。重在实现 p u s h push push p o p pop pop 操作。

  1. 对于 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),可以接受。

  1. 对于 p o p pop pop 操作,它等价于 p o p A t S t a c k popAtStack popAtStack 操作,将参数 i n d e x index index 设为数组最后位置。

  2. 对于 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

ac

致语

  • 理解思路很重要
  • 读者有问题请留言,清墨看到就会回复的。

相关文章:

力扣(LeetCode)1172. 餐盘栈(C++)

优先队列 解题思路&#xff1a;根据题意模拟。用数组存储无限数量的栈。重在实现 p u s h push push 和 p o p pop pop 操作。 对于 p u s h push push 操作&#xff0c;需要知道当前从左往右第一个空栈的下标。分两类讨论&#xff1a; ①所有栈都是满的&#xff0c;那么我…...

详细说一下DotNet Core 、DotNet5、DotNet6和DotNet7的简介和区别

.NET是一种用于构建多种应用的免费开源开发平台&#xff0c;可以使用多种语言&#xff0c;编辑器和库开发Web应用、Web API和微服务、云中的无服务器函数、云原生应用、移动应用、桌面应用、Windows WPF、Windows窗体、通用 Windows平台 (UWP)、游戏、物联网 (IoT)、机器学习、…...

基于MBD的控制系统建模与仿真软件工具集

随着新能源汽车和自动驾驶技术的快速发展&#xff0c;汽车电子电气架构的发展已成为汽车行业推陈出新的主要动力&#xff1a;车内电控系统变得越来越复杂、软件迭代周期越来越短&#xff0c;汽车电子软件开发和测试的质量与效率要求也越来越高。汽车电控系统的设计开发已然成为…...

QML动画分组(Grouped Animations)

通常使用的动画比一个属性的动画更加复杂。例如你想同时运行几个动画并把他们连接起来&#xff0c;或者在一个一个的运行&#xff0c;或者在两个动画之间执行一个脚本。动画分组提供了很好的帮助&#xff0c;作为命名建议可以叫做一组动画。有两种方法来分组&#xff1a;平行与…...

探索未来的数字人生:全景VR数字人

在数字化时代&#xff0c;人工智能和虚拟现实技术正日益成为我们生活中不可或缺的一部分。而全景VR数字人&#xff0c;则是这一时代的最新产品&#xff0c;吸引了越来越多的关注和研究。 一、什么是全景VR数字人&#xff1f; 全景VR数字人是一种通过虚拟现实技术创造的数字人形…...

计算机基础 -- 硬件篇

首先,经常提起得计算机硬件都有啥? CPU,内存条,影片,显卡,声卡,网卡,主板,机箱电源,键鼠,显示器,音响,摄像头等 本次介绍内容为台式机与笔记本电脑的内容混合.CPU CPU(中央处理器)包含了运算器和控制器.相当于计算机的"大脑",决定了运算速度的快慢.算是电脑"最…...

【高危】Apache Superset <2.1.0 认证绕过漏洞(POC)(CVE-2023-27524)

漏洞描述 Apache Superset 是一个开源的数据可视化和业务智能平台&#xff0c;可用于数据探索分析和数据可视化。 Apache Superset 受影响版本在使用默认的secret_key时&#xff0c;攻击者可通过默认的secret_key为任意用户生成有效的会话令牌&#xff0c;进而绕过验证造成信…...

vue3如果用setup写如何获取类似于vue2中的this

Vue 3 是一款用于构建用户界面的 JavaScript 框架。 在 Vue 3 中&#xff0c;SFC&#xff08;Single File Component&#xff09;的 API 风格发生了变化&#xff0c;新增了 setup 函数而废弃了之前版本的 options API。setup 函数被认为是 Vue 3 的精华所在&#xff0c;它可以让…...

关于 API接口的一些知识分享

一、安全性 API接口的安全性主要表现在&#xff1a; 1、 API接口的提供者是经过认证的&#xff0c;并且不会将自己的用户信息透露给第三方 2、 API接口不能被第三方窃取或篡改 3、 API接口是一个相对安全的 API&#xff0c;不会轻易地被第三方截获和破解 4、 API接口一般都…...

【ROS仿真实战】Gazebo仿真平台介绍及安装方法(一)

文章目录 前言一、Gazebo简介二、Gazebo仿真平台的基本概念三、Gazebo仿真平台的安装方法四、总结 前言 Gazebo仿真平台是一个广泛应用于机器人研发、测试和教育等领域的开源软件。它可以模拟机器人的运动、感知和控制等行为&#xff0c;并提供了丰富的物理引擎、传感器模拟和…...

Lychee图床 - 本地配置属于自己的相册管理系统并远程访问

文章目录 1.前言2. Lychee网站搭建2.1. Lychee下载和安装2.2 Lychee网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 图床作为图片集中存放的服务网站&#xff0c;可以看做是云存储的一部分&#xff0c;既可…...

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有什么用&#xff1f; 2、什么是wkhtmltopdf 3、wkhtmltopdf 参数介绍 4、示例项目 5、预览效果 1、htmltopdf有什么用&#xff1f; htmltopdf 是一款基于wkhtmltopdf技术的html转pdf文档java类库&#xff0c;支持html转pdf和url转pdf。 2、什么是wkhtmltopdf…...

设计模式-适配器模式

适配器模式 文章目录 适配器模式1、什么是适配器模式2、为什么要用适配器模式2.1、封装有缺陷的接口设计2.2、统一多个类的接口设计2.3、替换依赖的外部系统2.4、兼容老版本接口2.5、适配不同格式的数据 3、如何使用适配器模式1、类适配器2、对象适配器 总结 1、什么是适配器模…...

一款支持全文检索、工作流审批、知识图谱的企事业知识库

一、项目介绍 一款全源码&#xff0c;可二开&#xff0c;可基于云部署、私有部署的企业级知识库云平台&#xff0c;一款让企业知识变为实打实的数字财富的系统&#xff0c;应用在需要进行文档整理、分类、归集、检索、分析的场景。 获取方式q:262086839 为什么建立知识库平台&…...

SAP MRP例外信息解释

SAP中MRP的例外信息&#xff0c;一共分为八类&#xff0c;下面是所有例外信息的解释 第一类&#xff1a; 69&#xff1a;BOM组件可能是递归的&#xff0c;即自己的子集中包括了自己。 02&#xff1a;订单创建日期在过去&#xff0c;可能是没有及时处理&#xff0c;这个建议表…...

广义的S变换

广义的S变换 S变换中窗函数是高斯函数 1 2 π σ e − 1 2 σ t 2 \frac{1}{{\sqrt {2\pi } \sigma }}{e^{ - \frac{1}{{2\sigma }}{t^2}}} 2π ​σ1​e−2σ1​t2&#xff0c;它的形状由方差 σ 1 f \sigma\frac{1}{f} σf1​控制。许多研究表明&#xff0c;S变换中窗函数的…...

python异常及其捕获

文章目录 异常的捕获异常是可传递的 异常的捕获 1.为什么要捕获异常? 在可能发生异常的地方&#xff0c;进行捕获。当异常出现的时候&#xff0c;提供解决方式&#xff0c;而不是任由其导致程序无法运行。 2.捕获异常的语法? try: 可能要发生异常的语句 except 异常名 as 别…...

mysql实现存在则保存,不存在则更新

方式1 ON DUPLICATE KEY UPDATE 使用前提&#xff1a;表必须配置唯一键或者主键&#xff0c;且保存的字段中包含该键【重点】 原理&#xff1a; ON DUPLICATE KEY UPDATE如果配合主键&#xff0c;存在数据a&#xff0c;新插入b&#xff0c;如果主键不冲突&#xff0c;会保存b…...

Phi-4-mini-reasoning实际作品:15个跨学科逻辑题(数学/哲学/计算机)解答集

Phi-4-mini-reasoning实际作品&#xff1a;15个跨学科逻辑题&#xff08;数学/哲学/计算机&#xff09;解答集 1. 模型能力概览 Phi-4-mini-reasoning是一个专注于推理任务的文本生成模型&#xff0c;特别擅长处理需要多步逻辑推导的问题。与通用聊天模型不同&#xff0c;它被…...

3大场景解放双手:SteamShutdown智能管理下载与自动控制电脑的完整方案

3大场景解放双手&#xff1a;SteamShutdown智能管理下载与自动控制电脑的完整方案 【免费下载链接】SteamShutdown Automatic shutdown after Steam download(s) has finished. 项目地址: https://gitcode.com/gh_mirrors/st/SteamShutdown 你是否曾在深夜开启游戏下载后…...

从‘翻车’到稳定:手把手教你用Matlab极点配置驯服小车倒立摆(附Simulink模型)

用Matlab极点配置实现小车倒立摆的精准控制&#xff1a;从理论到Simulink实战 倒立摆系统作为控制理论中的经典案例&#xff0c;完美展现了动态系统稳定控制的挑战与魅力。想象一下&#xff0c;一根垂直向上的杆子放在移动小车上&#xff0c;任何微小的扰动都会导致杆子倾倒——…...

MarkDownload:如何用浏览器扩展解决网页内容保存的三大痛点

MarkDownload&#xff1a;如何用浏览器扩展解决网页内容保存的三大痛点 【免费下载链接】markdownload A Firefox and Google Chrome extension to clip websites and download them into a readable markdown file. 项目地址: https://gitcode.com/gh_mirrors/ma/markdownlo…...

AutoHotkey自动化效率提升指南:从入门到进阶的全场景应用技巧

AutoHotkey自动化效率提升指南&#xff1a;从入门到进阶的全场景应用技巧 【免费下载链接】antimicrox Graphical program used to map keyboard buttons and mouse controls to a gamepad. Useful for playing games with no gamepad support. 项目地址: https://gitcode.co…...

推荐8款提升论文效率的AI工具(含爱毕业aibiye)和简易使用教程

在学术研究领域&#xff0c;AI技术的应用显著提升了论文写作的效率与质量。以下推荐8款功能强大的智能工具&#xff0c;涵盖文献解析、内容生成、文本优化等关键环节&#xff0c;助力研究者高效完成从资料收集到论文润色的全流程工作。这些创新解决方案能够有效简化研究过程&am…...

ESP32-S3玩转微雪2.8寸触摸屏:从零到LVGL的保姆级避坑指南(ESP-IDF 5.3)

ESP32-S3与微雪2.8寸触摸屏深度适配&#xff1a;LVGL全流程实战手册 刚拿到微雪2.8寸触摸屏开发板的开发者&#xff0c;往往既兴奋又忐忑——这块搭载ESP32-S3芯片、配备8M PSRAM的硬件平台&#xff0c;理论上能流畅运行LVGL图形库&#xff0c;但实际开发中总会遇到各种"坑…...

你的pip更新报错,可能和Python 3.4这个“老古董”有关 | 版本兼容性排查指南

当pip更新报错时&#xff1a;Python版本兼容性深度排查指南 在Linux服务器上执行pip install --upgrade pip时&#xff0c;屏幕上突然跳出一串红色错误日志——这可能是每位Python开发者都经历过的噩梦。更令人抓狂的是&#xff0c;明明按照官方文档操作&#xff0c;却依然卡在…...

来自硅谷的顶级外卖-Claude Code 源码泄露事件讨论

Claude Code 源码泄露事件全解析摘要&#xff1a;2026年3月&#xff0c;Anthropic 旗下 AI 编程工具 Claude Code 的完整源码被人通过匿名渠道公开。这次泄露撕开了这款"明星产品"的外衣——5层模块架构、20安全验证器、自研 Ink 渲染引擎、四层记忆系统。代码里没有…...

万象视界灵坛应用案例:博物馆数字藏品语义标注系统开发实录

万象视界灵坛应用案例&#xff1a;博物馆数字藏品语义标注系统开发实录 1. 项目背景与挑战 博物馆数字化进程中&#xff0c;海量文物藏品的语义标注一直是个难题。传统方法依赖人工标注&#xff0c;不仅效率低下&#xff0c;而且难以保证一致性。以某省级博物馆为例&#xff…...