当前位置: 首页 > 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运行可行…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...