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. 可以在查询过程中,…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
