开发者社区> ik1003> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

LeetCode每日一题——901. 股票价格跨度

简介: 编写一个 StockSpanner 类,它收集某些股票的每日报价,并返回该股票当日价格的跨度。
+关注继续查看

题目

编写一个 StockSpanner 类,它收集某些股票的每日报价,并返回该股票当日价格的跨度。

?

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数(从今天开始往回数,包括今天)。

?

例如,如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85],那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例

示例:

输入:[“StockSpanner”,“next”,“next”,“next”,“next”,“next”,“next”,“next”],

[[],[100],[80],[60],[70],[60],[75],[85]]

输出:[null,1,1,1,2,1,4,6]

解释:

首先,初始化 S = StockSpanner(),然后: S.next(100) 被调用并返回 1, S.next(80) 被调用并返回

1, S.next(60) 被调用并返回 1, S.next(70) 被调用并返回 2, S.next(60) 被调用并返回 1,

S.next(75) 被调用并返回 4, S.next(85) 被调用并返回 6。

?

注意 (例如) S.next(75) 返回 4,因为截至今天的最后 4 个价格 (包括今天的价格 75) 小于或等于今天的价格。

?

提示:

?

调用 StockSpanner.next(int price) 时,将有 1 <= price <= 10^5。

每个测试用例最多可以调用 10000 次 StockSpanner.next。

在所有测试用例中,最多调用 150000 次 StockSpanner.next。

此问题的总时间限制减少了 50%。

思路

单调栈,题中意思等价于寻找大于某元素上一个值,然后求坐标差值就是答案了。

这里由于题意,我们需要存储输入元素以及输入元素的下标,输入元素直接存入数组,下标存入单调栈,单调栈自栈顶到栈底递增,栈顶元素即为大于某一元素的上一个值的下标。

这里求差值时还需判断单调栈是否为空,如果为空说明某元素大于前方所有元素,这里返回下标+1即可

题解

class StockSpanner:

    def __init__(self):
        # 单调栈
        self.s = []
        # 输入元素数组
        self.num = []
        # 下标
        self.index = -1

    def next(self, price: int) -> int:
        self.index += 1
        # 从单调栈弹出元素
        while self.s and self.num[self.s[-1]] <= price:
            self.s.pop()
        # 求答案
        ans = self.index - self.s[-1] if self.s else self.index + 1
        # 更新单调栈以及输入元素数组
        self.s.append(self.index)
        self.num.append(price)
        return ans

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode每日一题——324. 摆动排序 II
给你一个整数数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
0 0
LeetCode每日一题题解:1189. “气球” 的最大数量
LeetCode每日一题题解:1189. “气球” 的最大数量
0 0
LeetCode每日一题——1184. 公交站间的距离
环形公交路线上有 n 个站,按次序从 0 到 n - 1 进行编号。
0 0
LeetCode每日一题——1200. 最小绝对差
给你个整数数组 arr,其中每个元素都 不相同。
0 0
LeetCode每日一题——719.找出第k小的数对距离
数对 (a,b) 由整数 a 和 b 组成,其数对距离定义为 a 和 b 的绝对差值。
0 0
LeetCode每日一题——515. 在每个树行中找最大值
给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
0 0
LeetCode每日一题——908. 最小差值 I
给你一个整数数组 nums,和一个整数 k 。
0 0
【leetcode】力扣 --- 日积月累,每日一题——7 有序数组的平方
有序数组的平方 一、题目 二、代码及思路 简单聊一下:临近期末了,一大堆论文接踵而至,今天写这个,明天写那个,突然发现今天的题还没刷。学习也还没有学习。昨天我导让我们开始看机器学习(西瓜书),兄弟们,如果有相关资源可以call我。I need you!!!
0 0
[leetcode/lintcode 题解] 算法面试高频题详解:股票价格跨度
[leetcode/lintcode 题解] 算法面试高频题详解:股票价格跨度
0 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载
http://www.vxiaotou.com