901. 股票代价跨度（难度：中等）

手机游戏开发者 · 2024-9-21 13:13:01

标题链接：https://leetcode.cn/problems/online-stock-span/

标题形貌：

编写一个 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%。

解法：栈

根据标题形貌，每次须要找到当前元素之前的小于即是本身的一连的元素个数。
那着实每次只须要关注，前面有多少个小于即是当前元素的个数，当元素小于遍历到的元素时，将不再关注前面的元素。
我们可以利用一个栈布局stack，内里每一个元素存放一个数组temp[2]，来存储前面的元素巨细temp[0]和小于即是该元素的个数temp[1]。
每次next时，就遍历栈，和栈首元素temp = stack.peekFirst()举行比力：

当price <= temp[0] 时，将栈首元素出栈，并将元素个数加上栈首元素中的个数，即 result += temp[1]。
当price > temp[0] 时，则退出栈遍历。

末了将该元素的巨细和小于即是该元素的个数入栈。
代码：

901. 股票代价跨度（难度：中等）

所属分类: 问答交流

新帖推荐: 30日

推荐作品