Leetcode.901 股票价格跨度
题目链接
Leetcode.901 股票价格跨度 Rating : 1709
题目描述
设计一个算法收集某些股票的每日报价,并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。
- 例如,如果未来 7 天股票的价格是
[100,80,60,70,60,75,85],那么股票跨度将是[1,1,1,2,1,4,6]。
实现 StockSpanner类:
StockSpanner()初始化类对象。int next(int price)给出今天的股价price,返回该股票当日价格的 跨度 。
示例:
输入:
[“StockSpanner”, “next”, “next”, “next”, “next”, “next”, “next”, “next”]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出:
[null, 1, 1, 1, 2, 1, 4, 6]解释: StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80); // 返回 1
stockSpanner.next(60); // 返回 1
stockSpanner.next(70); // 返回 2
stockSpanner.next(60); // 返回 1
stockSpanner.next(75); // 返回 4,因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。 stockSpanner.next(85); //返回 6
提示:
- 1<=price<=1051 <= price <= 10^51<=price<=105
- 最多调用
next方法 10410^4104 次
分析:
使用一个 单调栈stack,栈里面存的是 (price,idx)组成的二元组,里面只记录大于当前 price的二元组。
如果当前栈顶的二元组的price<= 当前price,就将栈顶元素弹出。这样操作之后,要么栈为空,要么栈顶元素就是左边第一个大于当前 price的二元组了。
用当前的 idx减去栈顶元素的 idx(栈为空,就减去 -1),差值就是当前 price的跨度。
时间复杂度:O(n)O(n)O(n)
C++代码:
using PII = pair<int,int>;
class StockSpanner {
public:int idx = 0;stack<PII> stk; StockSpanner() {}int next(int price) {while(!stk.empty() && stk.top().first <= price) stk.pop();int l = stk.empty() ? -1 : stk.top().second;int ans = idx - l;stk.push({price,idx++});return ans;}
};
Java代码:
class StockSpanner {int idx;Stack<int[]> stk;public StockSpanner() {idx = 0;stk = new Stack<>();}public int next(int price) {while(!stk.isEmpty() && stk.peek()[0] <= price) stk.pop();int l = stk.isEmpty() ? -1 : stk.peek()[1];int ans = idx - l;stk.push(new int[]{price,idx++});return ans;}
}
相关文章:
Leetcode.901 股票价格跨度
题目链接 Leetcode.901 股票价格跨度 Rating : 1709 题目描述 设计一个算法收集某些股票的每日报价,并返回该股票当日价格的 跨度 。 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,…...
vue入门(四)组件基础,$emits简单用法
上一篇:vue入门(三)事件(方法)处理、侦听器、模板引用 1.组件最基础的用法: 首先有一个button.vue的组件,里面只画了一个按钮 button.vue: <script> export default({data(){return{but…...
VBA提高篇_27 OptionBOX_CheckBox_Frame_Image_VBA附加控件
文章目录1.单选按钮OptionBOX:2.复选框CheckBox:3.框架Frame:4.图像Image: (loadPictrue)5. VBA附加控件:6. 适用于很多控件的重要属性:1.单选按钮OptionBOX: 默认时,同一窗体的所有单选按钮均属于同一组,只能选中一个 可通过Frame控件进行分组解决. 2.复选框CheckBox: 一次可以…...
STM32开发(11)----CubeMX配置独立看门狗(IWDG)
CubeMX配置独立看门狗(IWDG)前言一、独立看门狗的介绍二、实验过程1.STM32CubeMX配置独立看门狗2.代码实现3.硬件连接4.实验结果总结前言 本章介绍使用STM32CubeMX对独立看门狗定时器进行配置的方法。门狗本质上是一个定时器,提供了更高的安…...
医疗方案 | 星辰天合入选“2022智慧新医信优秀解决方案”
近日,由 HC3i数字医疗网主办的《数字化转型驱动下的医院高质量发展论坛》暨 2022 智慧新医信优秀解决方案发布仪式在线上召开。XSKY星辰天合的“智慧医疗软件定义数据基础设施”解决方案成功入选 2022 智慧新医信优秀解决方案,。此次论坛由 HC3i 数字医疗…...
【系统服务实战】tomcat服务的安装实战
未来要更新的专栏(此表格后面会继续完善) 专栏系列学习路线完成情况云原生系列linux基本功系列-基础命令汇总已更新51个命令云原生系列linux基本功系列-系统服务实战正在更新文章目录前言一. tomcat的概述1.1 什么是tomcat1.2 tomcat的官网二. tomcat单…...
【图文详解】Unity存储游戏数据的几种方法
Unity3D存储游戏数据的方式1 PlayerPrefs: Unity自带的一种简单的键值存储系统2 ScriptableObject: Unity中最灵活的数据管理工具2.1 如何手动创建和修改数据文件2.2 ScriptableObject优缺点总结3 JSON: 轻量级的数据交换格式3.1 序列化与反序列化3.2 用JsonUtility对对象进行序…...
SESAM 安装教程
SESAM (Super Element Structure Analysis Module)是由挪威船级社(DNV-GL)开发的一款有限元分析(FEA)系统,它以 GeniE、HydroD 和 DeepC 等模块为核心,主要用于海工结构的强度评估、…...
语言文件操作
🌱博客主页:大寄一场. 🌱系列专栏:C语言学习笔记 😘博客制作不易欢迎各位👍点赞⭐收藏➕关注 目录 前言 C语言中的文件打开和关闭 文件指针 文件的打开和关闭 fclose 文件的顺序读写 fseek ftell …...
Java面试题--熔断和降级的区别
熔断和降级都是系统自我保护的一种机制,但二者又有所不同,它们的区别主要体现在以下几点: 概念不同 触发条件不同 归属关系不同 1.概念不同 1.1熔断概念 “熔断”一词早期来自股票市场。熔断(Circuit Breaker)也…...
阅读笔记5——深度可分离卷积
一、标准卷积 标准卷积在卷积时,同时考虑了特征图的区域和通道信息。 标准卷积的过程如图1-1所示,假设输入特征图的channel3,则每个卷积核的channel都为3,每个卷积核的3个channel对应提取输入特征图的3个channel的特征(…...
Microsoft Dynamics 365:导入License到服务层,通过Business Central Administration Shell
本文主要是Microsoft Dynamics 365的License导入的图解干货,不多赘述,直接上图:第一步:准备好的License文件放在你喜欢的目录下第二步:到开始程序里找到并打开 Business Central Administration Shell3.第三步…...
centos6.10安装FastDfs出错的问题
在centos6.10虚拟机安装dfs文件服务器时,安装报错,报错为: gcc: error trying to exec cc1’: execvp: 没有那个文件或目录 1.ping www.baidu.con 排查网络是否通 2.yum update 排查yum源是否可用 3.yum源地址不可用时,修改yu…...
基础组件之内存池
内存池技术 操作系统在运行进程的过程中,会产生内存碎片,降低了内存的使用率。内存池技术就是为了解决/减少内存碎片的一种方法,内部底层的具体实现根据不同业务场景使用不要的方式,以下是一种好理解的方式,供大家一起…...
前端面试题--了解并简单介绍一下typescript
前端面试题–了解并简单介绍一下typescript TypeScript是JavaScript的超集,具有可选的类型并可以编译为纯JavaScript。 从技术上讲TypeScript就是具有静态类型的 JavaScript 。 向JavaScript添加静态类型的原因是什么?我想原因至少有三个: …...
【pytorch】ModuleList 与 ModuleDict
ModuleList 与 ModuleDict1、ModuleList2、ModuleDict3、总结1、ModuleList 1)ModuleList 接收一个子模块的列表作为输入,然后也可以类似 List 那样进行 append 和 extend 操作: net nn.ModuleList([nn.Linear(784, 256), nn.ReLU()]) net.append(nn.…...
Hive窗口函数语法规则、窗口聚合函数、窗口表达式、窗口排序函数 - ROW NUMBER 、口排序函数 - NTILE、窗口分析函数
Hive窗口函数 文章目录Hive窗口函数语法规则窗口聚合函数窗口表达式窗口排序函数 - ROW NUMBER窗口排序函数 - NTILE窗口分析函数窗口函数也叫开窗函数、OLAP函数其最大特点:输入值是从SELECT语句的结果集中的一行或多行的“窗口”中获取的。如果函数具有OVER子句&a…...
Go设计模式之函数选项模式
目录引入函数选项模式(functional options pattern)可选参数默认值接口类型版本引入 假设现在需要定义一个包含多个配置项的结构体,具体定义如下: // DoSomethingOption 定义配置项 type DoSomethingOption struct {// a 配置aa…...
ClickHouse 数据类型、函数大小写敏感性
这里写自定义目录标题SELECT *FROM system.data_type_families注意:case_insensitive0 表示大小写敏感。 ClickHouse 的 String 类型、Int 类型、Float 类型、Decimal类型等都是大小写敏感的(case_sensitive0)。关于ClickHouse大小写敏感&am…...
nodejs基于vue 网上商城购物系统
可定制框架:ssm/Springboot/vue/python/PHP/小程序/安卓均可开发 目录 1 绪论 1 1.1课题背景 1 1.2课题研究现状 1 1.3初步设计方法与实施方案 2 1.4本文研究内容 2 2 系统开发环境 4 2. 3 系统分析 6 3.1系统可行性分析 6 3.1.1经济可行性 6 3.1.2技术可行性 6 3.1.3运行可行…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
