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

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 &#xff1a; 1709 题目描述 设计一个算法收集某些股票的每日报价&#xff0c;并返回该股票当日价格的 跨度 。 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数&#xff08;从今天开始往回数&#xff0c;…...

vue入门(四)组件基础,$emits简单用法

上一篇&#xff1a;vue入门&#xff08;三&#xff09;事件&#xff08;方法&#xff09;处理、侦听器、模板引用 1.组件最基础的用法&#xff1a; 首先有一个button.vue的组件&#xff0c;里面只画了一个按钮 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配置独立看门狗&#xff08;IWDG&#xff09;前言一、独立看门狗的介绍二、实验过程1.STM32CubeMX配置独立看门狗2.代码实现3.硬件连接4.实验结果总结前言 本章介绍使用STM32CubeMX对独立看门狗定时器进行配置的方法。门狗本质上是一个定时器&#xff0c;提供了更高的安…...

医疗方案 | 星辰天合入选“2022智慧新医信优秀解决方案”

近日&#xff0c;由 HC3i数字医疗网主办的《数字化转型驱动下的医院高质量发展论坛》暨 2022 智慧新医信优秀解决方案发布仪式在线上召开。XSKY星辰天合的“智慧医疗软件定义数据基础设施”解决方案成功入选 2022 智慧新医信优秀解决方案&#xff0c;。此次论坛由 HC3i 数字医疗…...

【系统服务实战】tomcat服务的安装实战

未来要更新的专栏&#xff08;此表格后面会继续完善&#xff09; 专栏系列学习路线完成情况云原生系列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 &#xff08;Super Element Structure Analysis Module&#xff09;是由挪威船级社&#xff08;DNV-GL&#xff09;开发的一款有限元分析&#xff08;FEA&#xff09;系统&#xff0c;它以 GeniE、HydroD 和 DeepC 等模块为核心&#xff0c;主要用于海工结构的强度评估、…...

语言文件操作

&#x1f331;博客主页&#xff1a;大寄一场. &#x1f331;系列专栏&#xff1a;C语言学习笔记 &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 目录 前言 C语言中的文件打开和关闭 文件指针 文件的打开和关闭 fclose 文件的顺序读写 fseek ftell …...

Java面试题--熔断和降级的区别

熔断和降级都是系统自我保护的一种机制&#xff0c;但二者又有所不同&#xff0c;它们的区别主要体现在以下几点&#xff1a; 概念不同 触发条件不同 归属关系不同 1.概念不同 1.1熔断概念 “熔断”一词早期来自股票市场。熔断&#xff08;Circuit Breaker&#xff09;也…...

阅读笔记5——深度可分离卷积

一、标准卷积 标准卷积在卷积时&#xff0c;同时考虑了特征图的区域和通道信息。 标准卷积的过程如图1-1所示&#xff0c;假设输入特征图的channel3&#xff0c;则每个卷积核的channel都为3&#xff0c;每个卷积核的3个channel对应提取输入特征图的3个channel的特征&#xff08…...

Microsoft Dynamics 365:导入License到服务层,通过Business Central Administration Shell

本文主要是Microsoft Dynamics 365的License导入的图解干货&#xff0c;不多赘述&#xff0c;直接上图&#xff1a;第一步&#xff1a;准备好的License文件放在你喜欢的目录下第二步&#xff1a;到开始程序里找到并打开 Business Central Administration Shell3.第三步&#xf…...

centos6.10安装FastDfs出错的问题

在centos6.10虚拟机安装dfs文件服务器时&#xff0c;安装报错&#xff0c;报错为&#xff1a; gcc: error trying to exec cc1’: execvp: 没有那个文件或目录 1.ping www.baidu.con 排查网络是否通 2.yum update 排查yum源是否可用 3.yum源地址不可用时&#xff0c;修改yu…...

基础组件之内存池

内存池技术 操作系统在运行进程的过程中&#xff0c;会产生内存碎片&#xff0c;降低了内存的使用率。内存池技术就是为了解决/减少内存碎片的一种方法&#xff0c;内部底层的具体实现根据不同业务场景使用不要的方式&#xff0c;以下是一种好理解的方式&#xff0c;供大家一起…...

前端面试题--了解并简单介绍一下typescript

前端面试题–了解并简单介绍一下typescript TypeScript是JavaScript的超集&#xff0c;具有可选的类型并可以编译为纯JavaScript。 从技术上讲TypeScript就是具有静态类型的 JavaScript 。 向JavaScript添加静态类型的原因是什么&#xff1f;我想原因至少有三个&#xff1a; …...

【pytorch】ModuleList 与 ModuleDict

ModuleList 与 ModuleDict1、ModuleList2、ModuleDict3、总结1、ModuleList 1&#xff09;ModuleList 接收一个子模块的列表作为输入&#xff0c;然后也可以类似 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函数其最大特点&#xff1a;输入值是从SELECT语句的结果集中的一行或多行的“窗口”中获取的。如果函数具有OVER子句&a…...

Go设计模式之函数选项模式

目录引入函数选项模式&#xff08;functional options pattern&#xff09;可选参数默认值接口类型版本引入 假设现在需要定义一个包含多个配置项的结构体&#xff0c;具体定义如下&#xff1a; // DoSomethingOption 定义配置项 type DoSomethingOption struct {// a 配置aa…...

ClickHouse 数据类型、函数大小写敏感性

这里写自定义目录标题SELECT *FROM system.data_type_families注意&#xff1a;case_insensitive0 表示大小写敏感。 ClickHouse 的 String 类型、Int 类型、Float 类型、Decimal类型等都是大小写敏感的&#xff08;case_sensitive0&#xff09;。关于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运行可行…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

深入理解JavaScript设计模式之单例模式

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

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...