【10.10】队列-设计自助结算系统
一、题目
请设计一个自助结账系统,该系统需要通过一个队列来模拟顾客通过购物车的结算过程,需要实现的功能有:
get_max()
:获取结算商品中的最高价格,如果队列为空,则返回 -1add(value)
:将价格为value
的商品加入待结算商品队列的尾部remove()
:移除第一个待结算的商品价格,如果队列为空,则返回 -1
注意,为保证该系统运转高效性,以上函数的均摊时间复杂度均为 O(1)
示例 1:
输入: ["Checkout","add","add","get_max","remove","get_max"] [[],[4],[7],[],[],[]]输出: [null,null,null,7,4,7]
示例 2:
输入: ["Checkout","remove","get_max"] [[],[],[]]输出: [null,-1,-1]
提示:
1 <= get_max, add, remove 的总操作数 <= 10000
1 <= value <= 10^5
二、解题思路
我们可以使用单调的双端队列来解决,该方法的精髓在于通过保持队列的单调递减顺序来高效地解决最大值查询问题。算法的关键洞见是:一旦新元素被加入队列,它之前的所有较小的元素都不再可能成为最大值。这一点通过维护一个严格递减的双端队列得以实现,具体过程如下:
核心原理
以一个数字序列例如 [1, 1, 1, 1, 2] 为例,一旦数字 2 被加入队列,所有在它之前的数字 1 都不再有可能成为最大值。这是因为在队列的出队操作中,数字 2 只会在所有数字 1 都被移除之后才可能被移除。换言之,任何时刻只要队列中有数字 1,数字 2 也必然在队列中,从而使得数字 1 对最大值的判断没有任何影响。这就揭示了维护队列单调递减的重要性——只有当队列中的每个元素都保证比它前面的元素大时,我们才能在 O(1) 的时间复杂度内查询到最大值。
实现机制
- **双端队列的应用**
使用双端队列可以从两端进行元素的添加和移除操作。在新元素加入时,我们从队列尾部开始,移除所有小于当前新元素的值,直到遇到一个更大的值或队列为空。这个过程保证了队列的单调递减特性。通过数学归纳法可以证明,如果在加入新元素之前队列是单调递减的,那么加入新元素后队列仍然是单调递减的。
- **辅助队列的配合**
除了双端队列,还需要一个辅助队列来记录所有加入的元素。这个辅助队列用来同步删除操作,确保当我们从双端队列的头部移除最大值时,辅助队列也相应地从头部移除元素。这样可以保持双端队列始终反映当前有效元素的最大值。
- **极值查询的优化**
由于队列的单调递减特性,查询当前最大值只需要简单地查看双端队列的首部元素。这样,原本需要遍历整个队列的操作被优化到了常数时间复杂度,大大提高了查询效率,特别是在需要频繁进行最大值查询的场景中。
总的来说,该算法通过巧妙地利用双端队列和辅助队列,实现了一个能够快速查询最大值的队列结构,对于需要实时处理数据并经常查询最大值的应用场景来说,这是一个极具效率的解决方案。
三、代码实现
#include <iostream>
#include <queue>
#include <deque>using namespace std;// Checkout 类,用于模拟一个结账队列,可以添加元素、移除元素以及获取队列中的最大值
class Checkout {queue<int> q; // 存储所有元素的队列deque<int> d; // 双端队列,用于维护队列中所有元素的最大值public:Checkout() {// 构造函数不需要任何操作}// 获取当前队列中的最大值int get_max() {if (d.empty())return -1; // 如果双端队列为空,则返回 -1return d.front(); // 返回双端队列的首元素,即最大值}// 向队列中添加一个新元素void add(int value) {// 从双端队列的尾部开始,移除所有小于新元素的值while (!d.empty() && d.back() < value) {d.pop_back();}d.push_back(value); // 在双端队列尾部添加新元素q.push(value); // 在队列尾部添加新元素}// 从队列中移除一个元素int remove() {if (q.empty())return -1; // 如果队列为空,则返回 -1int ans = q.front(); // 获取队列的首元素if (ans == d.front()) {d.pop_front(); // 如果队列的首元素是当前最大值,则也从双端队列中移除}q.pop(); // 从队列中移除首元素return ans; // 返回被移除的元素}
};int main() {// 示例 1Checkout checkout1;checkout1.add(4);checkout1.add(7);cout << checkout1.get_max() << endl; // 输出应为 7cout << checkout1.remove() << endl; // 输出应为 4cout << checkout1.get_max() << endl; // 输出应为 7// 示例 2Checkout checkout2;cout << checkout2.remove() << endl; // 输出应为 -1cout << checkout2.get_max() << endl; // 输出应为 -1return 0;
}
时间复杂度
-
add(int value)
函数:该函数中,我们在双端队列d
中添加元素之前,可能会移除一些元素。虽然这个操作看起来是在一个循环中,但每个元素最多只会被添加一次并最多被移除一次。因此,对于n
次add
操作,总的时间复杂度是 O(n)。这意味着单次add
操作的摊还时间复杂度是 O(1)。 -
remove()
函数:该函数中,我们移除队列q
中的元素,并且可能会移除双端队列d
中的元素(如果它是当前最大值)。这些操作都是常数时间的,因此remove
的时间复杂度是 O(1)。 -
get_max()
函数:该函数只是返回双端队列d
的首元素,是常数时间的操作,所以get_max
的时间复杂度是 O(1)。
空间复杂度
-
对于
Checkout
类,主要的空间消耗来自于存储元素的队列q
和双端队列d
。在最坏的情况下,如果没有元素被移除,这两个数据结构中都会存储所有添加的元素。 -
如果我们添加了
n
个元素,那么队列q
将包含n
个元素。双端队列d
在最坏的情况下(即所有元素都按递减顺序添加),也会包含n
个元素。因此,空间复杂度是 O(n)。
总结起来,对于 Checkout
类的每个操作,我们有:
- 时间复杂度:O(1)(对于
add
,是摊还的时间复杂度) - 空间复杂度:O(n)(其中
n
是添加到队列中的元素数量)
相关文章:
【10.10】队列-设计自助结算系统
一、题目 请设计一个自助结账系统,该系统需要通过一个队列来模拟顾客通过购物车的结算过程,需要实现的功能有: get_max():获取结算商品中的最高价格,如果队列为空,则返回 -1add(value):将价格为…...
android的ViewModel和LiveData 简介
ViewModel ViewModel 的优势 ViewModel 的替代方案是保存要在界面中显示的数据的普通类。在 activity 或 Navigation 目的地之间导航时,这可能会造成问题。此时,如果您不利用保存实例状态机制存储相应数据,系统便会销毁相应数据。ViewModel…...

Linux系统之free命令的基本使用
Linux系统之free命令的基本使用 一、free命令介绍二、free命令的使用帮助2.1 free命令的帮助信息2.2 free命令帮助解释 三、free命令的基本使用3.1 显示内存使用情况3.2 新增总计条目3.3 显示内存详细信息 四、注意事项 一、free命令介绍 free 命令是 Linux 系统中用于显示系统…...
大模型赋能网络安全整体应用流程概述
一、四个阶段概述 安全大模型的应用大致可以分为四个阶段: 阶段一主要基于开源基础模型训练安全垂直领域的模型; 阶段二主要基于阶段一训练出来的安全大模型开展推理优化、蒸馏等工序,从而打造出不同安全场景的专家模型,比如数据安全领域、安全运营领域、调用邮件识别领…...

SpringCloud - Nacos注册/配置中心
前言 该博客为Nacos学习笔记,主要目的是为了帮助后期快速复习使用 学习视频:7小快速通关SpringCloud 辅助文档:SpringCloud快速通关 一、简介 Nacos官网:https://nacos.io/docs/next/quickstart/quick-start/ Nacos /nɑ:kəʊ…...
面试准备——Java理论高级【笔试,面试的核心重点】
集合框架 Java集合框架是面试中的重中之重,尤其是对List、Set、Map的实现类及其底层原理的考察。 1. List ArrayList: 底层是动态数组,支持随机访问(通过索引),时间复杂度为O(1)。插入和删除元素时&#…...

AI伴读-清华大学104页《DeepSeek:从入门到精通》
辅助工具:deepseek、豆包AI伴读 官网:DeepSeekDeepSeek, unravel the mystery of AGI with curiosity. Answer the essential question with long-termism.https://www.deepseek.com/https://www.deepseek.com/清华大学104页《DeepSeek:从入…...

unity学习34:角色相关3,触发器trigger,铰链 hingejoint 等 spring joint, fixed joint
目录 1 触发的实现条件 1.1 碰撞的的实现条件 1.2 触发的实现条件 1.3 触发器trigger,直接拿 碰撞器collider修改下配置即可 2 触发器相关实验:触发开门效果 2.0 目标 2.1 player物体的属性 2.2 新建一个trigger 物体 2.3 新建一个被trigger 控…...

HarmonyOS Next 方舟字节码文件格式介绍
在开发中,可读的编程语言要编译成二进制的字节码格式才能被机器识别。在HarmonyOS Next开发中,arkts会编译成方舟字节码。方舟字节码长什么样呢?我们以一个demo编译出的abc文件: 二进制就是长这样,怎么去理解呢&…...

计算机视觉语义分割——Attention U-Net(Learning Where to Look for the Pancreas)
计算机视觉语义分割——Attention U-Net(Learning Where to Look for the Pancreas) 文章目录 计算机视觉语义分割——Attention U-Net(Learning Where to Look for the Pancreas)摘要Abstract一、Attention U-Net1. 基本思想2. Attention Gate模块3. 软注意力与硬注意力4. 实验…...

html 列动态布局
样式说明: /* 列动态布局,列之间以空格填充 */ li {display: flex;/* flex-direction: column; */justify-content: space-between; }...

DeepSeek开源多模态大模型Janus-Pro部署
DeepSeek多模态大模型部署 请自行根据电脑配置选择合适环境配置安装conda以及gitJanus 项目以及依赖安装运行cpu运行gpu运行 进入ui界面 请自行根据电脑配置选择合适 本人家用电脑为1060,因此部署的7B模型。配置高的可以考虑更大参数的模型。 环境配置 安装conda…...

DeepSeek结合Langchain的基本用法
DeepSeek结合Langchain的基本用法 DeepSeek 基于Openai接口规范的Prompt应答Deepseek结合LangchainDeepSeek 基于langchain的结构化返回 DeepSeek 基于Openai接口规范的Prompt应答 首先我们需要先基于pip 安装 pip install openai最开始我们先熟悉如何使用openai的接口规范&a…...

Redis持久化的两种方式:RDB和AOF
redis中的数据存储在缓存中,如果没有持久化的策略,Redis一旦宕机,那么将会导致数据丢失;因此redis提供了以下两种持久化方式:RDB和AOF 一般来说,大部分公司对这两种方式都是同时开启的 一、RDB RDB策略全…...
每日一题——131.分割回文串
题目链接:131. 分割回文串 - 力扣(LeetCode) 代码: class Solution { private:vector<vector<string>> result;vector<string> path;void backtracking (const string& s,int startindex){if(startindex …...

内容中台赋能人工智能技术提升业务创新能力
内容概要 在当今快速变化的市场环境中,企业需要不断寻求创新以保持竞争力。内容中台作为一种新型的内容管理架构,能够极大地提升企业在内容创建、管理和分发方面的效率。通过与人工智能技术的深度融合,企业能够将海量的数据和信息转化为有价…...

第七节 文件与流
基本的输入输出(iostream) C标准库提供了一组丰富的输入/输出功能,C的I/O发生在流中,流是字节序列。如果字节流是从设备(键盘、磁盘驱动器、网络连接等)流向内存,叫做输入操作。如果字节流是从…...

软件工程 项目管理
软件项目管理中可以分成两部分: 软件创新 软件项目管理项目是定义明确的任务,这是为了实现某个目标(例如,软件开发和交付)进行的一系列操作的集合。一个项目可以表征为: 每个项目都可以有一个独特而鲜明的目标。 项目不是日常活…...
通过类加载和初始化的一些题目理解Java类加载过程
通过题目重点理解:Class加载流程和运行时区域 目录 子类和父类static变量父子类加载顺序2class.forName初始化 子类和父类static变量 class Parent {static int a 1;static int b 2;static int c;static {c 3;System.out.println("parent static block&quo…...
LLMs之DeepSeek r1:TinyZero的简介、特点、安装和使用方法、案例应用Logic-RL的简介、安装和使用方法、案例应用之详细攻略
LLMs之DeepSeek r1:TinyZero的简介、特点、安装和使用方法、案例应用Logic-RL的简介、安装和使用方法、案例应用之详细攻略 目录 TinyZero的简介 1、TinyZero的特点 TinyZero的安装和使用方法 1、安装 创建 conda 环境 数据准备 (倒计时任务) 多GPU (适用于 …...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...