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

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...