百度制作企业网站多少钱,网站发布和推广,html制作简单个人主页代码,wordpress带汉字图片不显示一、题目 请设计一个自助结账系统#xff0c;该系统需要通过一个队列来模拟顾客通过购物车的结算过程#xff0c;需要实现的功能有#xff1a;
get_max()#xff1a;获取结算商品中的最高价格#xff0c;如果队列为空#xff0c;则返回 -1add(value)#xff1a;将价格为…一、题目 请设计一个自助结账系统该系统需要通过一个队列来模拟顾客通过购物车的结算过程需要实现的功能有
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 的总操作数 100001 value 10^5 二、解题思路 我们可以使用单调的双端队列来解决该方法的精髓在于通过保持队列的单调递减顺序来高效地解决最大值查询问题。算法的关键洞见是一旦新元素被加入队列它之前的所有较小的元素都不再可能成为最大值。这一点通过维护一个严格递减的双端队列得以实现具体过程如下
核心原理 以一个数字序列例如 [1, 1, 1, 1, 2] 为例一旦数字 2 被加入队列所有在它之前的数字 1 都不再有可能成为最大值。这是因为在队列的出队操作中数字 2 只会在所有数字 1 都被移除之后才可能被移除。换言之任何时刻只要队列中有数字 1数字 2 也必然在队列中从而使得数字 1 对最大值的判断没有任何影响。这就揭示了维护队列单调递减的重要性——只有当队列中的每个元素都保证比它前面的元素大时我们才能在 O(1) 的时间复杂度内查询到最大值。
实现机制
- **双端队列的应用** 使用双端队列可以从两端进行元素的添加和移除操作。在新元素加入时我们从队列尾部开始移除所有小于当前新元素的值直到遇到一个更大的值或队列为空。这个过程保证了队列的单调递减特性。通过数学归纳法可以证明如果在加入新元素之前队列是单调递减的那么加入新元素后队列仍然是单调递减的。
- **辅助队列的配合** 除了双端队列还需要一个辅助队列来记录所有加入的元素。这个辅助队列用来同步删除操作确保当我们从双端队列的头部移除最大值时辅助队列也相应地从头部移除元素。这样可以保持双端队列始终反映当前有效元素的最大值。
- **极值查询的优化** 由于队列的单调递减特性查询当前最大值只需要简单地查看双端队列的首部元素。这样原本需要遍历整个队列的操作被优化到了常数时间复杂度大大提高了查询效率特别是在需要频繁进行最大值查询的场景中。 总的来说该算法通过巧妙地利用双端队列和辅助队列实现了一个能够快速查询最大值的队列结构对于需要实时处理数据并经常查询最大值的应用场景来说这是一个极具效率的解决方案。 三、代码实现
#include iostream
#include queue
#include dequeusing namespace std;// Checkout 类用于模拟一个结账队列可以添加元素、移除元素以及获取队列中的最大值
class Checkout {queueint q; // 存储所有元素的队列dequeint 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 是添加到队列中的元素数量
