【算法挑战】设计一个支持增量操作的栈(含解析、源码)

1381.设计一个支持增量操作的栈

https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/

  • 1381.设计一个支持增量操作的栈
    • 题目描述
    • 方法 1: 用数组或链表模拟栈
      • 数组
      • 复杂度分析
      • 链表
      • 复杂度分析
      • 代码
    • 方法 2: 空间换时间
      • 图解
      • 复杂度分析
      • 代码

题目描述

请你设计一个支持下述操作的栈。实现自定义栈类 CustomStack :CustomStack(int maxSize):用 maxSize 初始化对象,maxSize 是栈中最多能容纳的元素数量,栈在增长到 maxSize 之后则不支持 push 操作。
void push(int x):如果栈还未增长到 maxSize ,就将 x 添加到栈顶。
int pop():弹出栈顶元素,并返回栈顶的值,或栈为空时返回 -1 。
void inc(int k, int val):栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ,则栈中的所有元素都增加 val 。示例:输入:
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出:
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释:
CustomStack customStack = new CustomStack(3); // 栈是空的 []
customStack.push(1);                          // 栈变为 [1]
customStack.push(2);                          // 栈变为 [1, 2]
customStack.pop();                            // 返回 2 --> 返回栈顶值 2,栈变为 [1]
customStack.push(2);                          // 栈变为 [1, 2]
customStack.push(3);                          // 栈变为 [1, 2, 3]
customStack.push(4);                          // 栈仍然是 [1, 2, 3],不能添加其他元素使栈大小变为 4
customStack.increment(5, 100);                // 栈变为 [101, 102, 103]
customStack.increment(2, 100);                // 栈变为 [201, 202, 103]
customStack.pop();                            // 返回 103 --> 返回栈顶值 103,栈变为 [201, 202]
customStack.pop();                            // 返回 202 --> 返回栈顶值 202,栈变为 [201]
customStack.pop();                            // 返回 201 --> 返回栈顶值 201,栈变为 []
customStack.pop();                            // 返回 -1 --> 栈为空,返回 -1提示:1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
每种方法 increment,push 以及 pop 分别最多调用 1000 次来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/design-a-stack-with-increment-operation
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法 1: 用数组或链表模拟栈

数组

使用数组来模拟栈,可以实现时间复杂度 O ( 1 ) O(1) O(1)pushpop,和 O ( k ) O(k) O(k)inc,剩下的就跟着题目描述来实现就好了。

  • 当栈元素个数等于 maxSize 时不允许继续入栈;
  • 当栈为空时,出栈操作返回 -1;
  • 增量操作时,当栈元素多于 k 个,将栈底的 k 个元素都加 val,栈元素少于 k 个时将所有元素都加上 val

复杂度分析

  • 时间复杂度:pushpop O ( 1 ) O(1) O(1)inc O ( k ) O(k) O(k)
  • 空间复杂度: O ( m a x S i z e ) O(maxSize) O(maxSize)

链表

也可以使用链表来模拟栈,入栈出栈都只操作 head,也能实现时间复杂度 O ( 1 ) O(1) O(1)pushpop 操作,但 inc 操作的话,由于找到从链表尾端开始的第 k 个元素 (可以用双指针来找) 的时间复杂度是 O ( n ) O(n) O(n),然后将链表尾端的 k 个元素进行增量操作的时间复杂度是 O ( k ) O(k) O(k),所以增量操作总的时间复杂度是 O ( n + k ) O(n+k) O(n+k)

复杂度分析

  • 时间复杂度:pushpop O ( 1 ) O(1) O(1)inc O ( n + k ) O(n+k) O(n+k)
  • 空间复杂度: O ( m a x S i z e ) O(maxSize) O(maxSize)

代码

JavaScript Code

/*** @param {number} maxSize*/
var CustomStack = function (maxSize) {this.list = [];this.maxSize = maxSize;
};/*** @param {number} x* @return {void}*/
CustomStack.prototype.push = function (x) {if (this.list.length < this.maxSize) {this.list.push(x);}
};/*** @return {number}*/
CustomStack.prototype.pop = function () {const item = this.list.pop();return item === void 0 ? -1 : item;
};/*** @param {number} k* @param {number} val* @return {void}*/
CustomStack.prototype.increment = function (k, val) {for (let i = 0; i < k && i < this.list.length; i++) {this.list[i] += val;}
};/*** Your CustomStack object will be instantiated and called as such:* var obj = new CustomStack(maxSize)* obj.push(x)* var param_2 = obj.pop()* obj.increment(k,val)*/

Python Code

class CustomStack(object):def __init__(self, maxSize):""":type maxSize: int"""self.list = []self.maxSize = maxSizedef size(self):return len(self.list)def push(self, x):""":type x: int:rtype: None"""if self.size() < self.maxSize:self.list.append(x)def pop(self):""":rtype: int"""return -1 if self.size() == 0 else self.list.pop()def increment(self, k, val):""":type k: int:type val: int:rtype: None"""size = k if k < self.size() else self.size()for i in range(0, size):self.list[i] += val# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

方法 2: 空间换时间

其实我们只在出栈时才关心元素的值,所以在增量操作的时候,可以不用去更新栈内的元素,而是用一个 hashMap 来记录第几个元素需要增加多少。出栈时,检查当前元素的下标是否在 hashMap 中有记录,有的话就加上增量再出栈。这样我们就得到了时间复杂度 O ( 1 ) O(1) O(1) 的增量操作,不过代价就是额外的 O ( N ) O(N) O(N) 空间。

图解

在这里插入图片描述

复杂度分析

  • 时间复杂度:push, popinc 都是 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( m a x S i z e ) O(maxSize) O(maxSize),模拟栈的数组和哈希表的空间都是 O ( m a x S i z e ) O(maxSize) O(maxSize)

代码

JavaScript Code

/*** @param {number} maxSize*/
var CustomStack = function (maxSize) {this.list = [];this.maxSize = maxSize;this.hashMap = {};
};/*** @param {number} key* @param {number} value* @return {void}*/
CustomStack.prototype._setInc = function (key, value) {if (!(key in this.hashMap)) {this.hashMap[key] = 0;}this.hashMap[key] += value;
};/*** @param {number} key* @return {number}*/
CustomStack.prototype._getInc = function (key) {return this.hashMap[key] || 0;
};/*** @return {number}*/
CustomStack.prototype._size = function () {return this.list.length;
};/*** @param {number} x* @return {void}*/
CustomStack.prototype.push = function (x) {if (this._size() < this.maxSize) {this.list.push(x);}
};/*** @return {number}*/
CustomStack.prototype.pop = function () {const top = this._size() - 1;const inc = this._getInc(top);let item = this.list.pop();if (item === void 0) {return -1;}item += inc;const newTop = top - 1;this._setInc(newTop, inc);this.hashMap[top] = 0;return item;
};/*** @param {number} k* @param {number} val* @return {void}*/
CustomStack.prototype.increment = function (k, val) {const size = this._size();k = k < size ? k - 1 : size - 1;this._setInc(k, val);
};/*** Your CustomStack object will be instantiated and called as such:* var obj = new CustomStack(maxSize)* obj.push(x)* var param_2 = obj.pop()* obj.increment(k,val)*/

总结

以上就是本文所有内容了,希望能对你有所帮助,能够解决设计一个支持增量操作的栈问题。

如果你喜欢本文,也请务必点赞、收藏、评论、转发,这会对我有非常大的帮助。请我喝杯冰可乐也是极好的!

已完结,欢迎持续关注。下次见~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/177551.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

与云栖的浪漫邂逅:记一段寻找云端之美的旅程

云端之旅 2023 年的云栖大会如约而至&#xff0c;这次云栖大会也是阿里新任掌门蔡老板当任阿里巴巴董事局主席以来的第一次。大会与以往有很多不一样的地方&#xff0c;其中 AIGC 更是本届大会的重点议题&#xff01;你会感叹&#xff0c;阿里还是猛啊&#xff01; 我逛了下展…

算法学习打卡day40|343. 整数拆分、96.不同的二叉搜索树

343. 整数拆分 力扣题目链接 题目描述&#xff1a; 给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1&#xff1a; 输入: n 2 输出: 1 解释: 2 1 …

一条 SQL 是如何在 MyBatis 中执行的

前言 MyBatis 执行 SQL 的核心接口为 SqlSession 接口&#xff0c;该接口提供了一些 CURD 及控制事务的方法&#xff0c;另外还可以通过 SqlSession 先获取 Mapper 接口的实例&#xff0c;然后通过 Mapper 接口执行 SQL&#xff0c;Mapper 接口方法的执行最终还是委托到 SqlSe…

Unity屏幕中涂鸦

LineRenderer LineRenderer是Unity中的一个组件&#xff0c;用于在场景中绘制简单的线段。 LineRenderer组件允许你通过设置一系列顶点来定义线段的形状和外观。它会根据这些顶点自动在场景中绘制出线段。 下面是LineRenderer的一些重要属性和方法&#xff1a; positionCou…

栈及其栈的模拟实现和使用

1. 栈(Stack) 1.1 概念 栈 &#xff1a;一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO &#xff08; Last In First Out &#xff09;的原则…

初识FFmpeg

前言 无意间见到群里的小伙伴展示视频工具。功能比较多&#xff0c;包括视频编码修改&#xff0c;画质处理&#xff0c;比例处理、名称提取&#xff0c;剪辑、标题拆解。因此开始了FFmpeg学习。以下摘自百度百科的解释。 FFmpeg是一套可以用来记录、转换数字音频、视频&#xf…

【Proteus仿真】【Arduino单片机】简易电子琴

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用无源蜂鸣器、按键等。 主要功能&#xff1a; 系统运行后&#xff0c;按下K1-K7键发出不同音调。 二、软件设计 /* 作者&#xff1a;嗨小易&a…

视频平台跨网级联视频压缩解决方案

一、 简介 视频监控领域对带宽有着较大的需求&#xff0c;这是因为视频流需要实时占用网络带宽资源。视频监控的传输带宽是组网结构的基础保障&#xff0c;关系到视频监控的稳定性、可靠性和可拓展性等因素。例如&#xff0c;720P的视频格式每路摄像头的比特率为2Mbps&#xff…

【机器学习合集】模型设计之网络宽度和深度设计 ->(个人学习记录笔记)

文章目录 网络宽度和深度设计1. 什么是网络深度1.1 为什么需要更深的模型浅层学习的缺陷深度网络更好拟合特征学习更加简单 2. 基于深度的模型设计2.1 AlexNet2.2 AlexNet工程技巧2.3 VGGNet 3. 什么是网络宽度3.1 为什么需要足够的宽度 4. 基于宽度模型的设计4.1 经典模型的宽…

在IDEA运行spark程序(搭建Spark开发环境)

建议大家写在Linux上搭建好Hadoop的完全分布式集群环境和Spark集群环境&#xff0c;以下在IDEA中搭建的环境仅仅是在window系统上进行spark程序的开发学习&#xff0c;在window系统上可以不用安装hadoop和spark&#xff0c;spark程序可以通过pom.xml的文件配置&#xff0c;添加…

【洛谷算法题】P5710-数的性质【入门2分支结构】

&#x1f468;‍&#x1f4bb;博客主页&#xff1a;花无缺 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 花无缺 原创 收录于专栏 【洛谷算法题】 文章目录 【洛谷算法题】P5710-数的性质【入门2分支结构】&#x1f30f;题目描述&#x1f30f;输入格式&a…

开源库存管理系统InvenTree的安装

本文是应网友 shijie880500 要求折腾的&#xff1b; 什么是 InvenTree &#xff1f; InvenTree 是一个开源的库存管理系统&#xff0c;提供强大的低级别库存控制和零件跟踪。InvenTree 系统的核心是 Python/Django 数据库后端&#xff0c;它提供了一个管理界面&#xff08;基于…

绝缘检测原理和绝缘电阻计算方法

文章目录 简介绝缘检测功能绝缘检测原理绝缘电阻检测的常用方法不平衡电桥法 绝缘电阻绝缘电阻的计算 绝缘检测开启或关闭为什么根据 V1 &#xff1c; V2 或 V1 ≥ V2 判断是上桥臂并入电阻还是下桥臂并入电阻 简介 绝缘检测是判断动力&#xff08;正、负&#xff09;总线与外…

Flutter三棵树的创建流程

一、Flutter常见的家族成员 Widget常见的家族成员 Element常见的家族成员 Render常见的家族成员 二、示例代码对应的Flutter Inspector树 示例代码&#xff1a;MyApp->MyHomePage->ErrorWidget&#xff0c;包含了StatelessWidget、StatefulWidget、LeafRenderObjectWid…

位运算与简单应用

一.位运算的基本概念&#xff1a; 首先&#xff0c;位运算是针对二进制的&#xff0c;(数字本来int,4字节,下面假设为1字节)。比如数字12&#xff0c;它的二进制本来是&#xff1a; 0000 0000 0000 0000 0000 0000 0000 1100 因为前面的数字大都是0&#xff0c;所以为了简写…

火影忍者游戏攻略大公开!成为忍者大师的秘诀揭秘

大家好&#xff01;作为火影忍者游戏的玩家&#xff0c;我们都希望能够在游戏中成为优秀的忍者大师&#xff0c;战胜强大的对手。为了帮助大家实现这一目标&#xff0c;我想分享一些实用的攻略和技巧。 首先&#xff0c;熟悉忍者技能是成为忍者大师的基础。在火影忍者游戏中&am…

C语言_自定义类型详解

文章目录 前言一.结构体的声明1.1结构体的基础知识1.2结构的声明1.3特殊声明1.4结构体的自引用在结构中包含一个类型为该结构本身的成员是否可以&#xff1f;正确的自引用方式匿名结构体类型和typedef的结合形式 1.5 结构体变量的定义和初始化结构体定义与初始化结构体里嵌套结…

【Linux进程】再谈软件—操作系统(Operator System)

目录 操作系统(Operator System) 概念 设计OS的目的 如何理解 "管理"——先描述再组织 系统调用和库函数概念 总结 操作系统(Operator System) 概念 任何计算机系统都包含一个基本的程序集合&#xff0c;称为操作系统(OS)。 笼统的理解&#xff0c;操作系统…

【python】路径管理+路径拼接问题

路径管理 问题相对路径问题绝对路径问题 解决os库pathlib库最终解决 问题 环境&#xff1a;python3.7.16 win10 相对路径问题 因为python的执行特殊性&#xff0c;使用相对路径时&#xff0c;在不同路径下用python指令会有不同的索引效果&#xff08;python的项目根目录根据执…