个人中心
文章发布
退出
作者热门文章
- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
28
4
题目地址：https://leetcode.com/problems/online-stock-span/description/
Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.
Thespan of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.
Forexample, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].
Example 1:
Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation:
First, S = StockSpanner() is initialized. Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.
Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.
Note:
1、 CallstoStockSpanner.next(intprice)willhave1<=price<=10^5.；
2、 Therewillbeatmost10000callstoStockSpanner.nextpertestcase.；
3、 Therewillbeatmost150000callstoStockSpanner.nextacrossalltestcases.；
4、 Thetotaltimelimitforthisproblemhasbeenreducedby75%forC++,and50%forallotherlanguages.；
这个题要我们求，当一个新的股票价格来到的时候，在这个天数过去的多少天内，股票的价格是小于等于今天的。注意的是，从今天向前面数已经经过的天数，今天也包括在内。
看了数值的范围，可以肯定这个题的时间复杂度必须在O(n)以内，也就是说平均每次next()方法调用的时候，必须在将近O(1)的时间内找到前面多少天的价格是小于等于今天的。
这个题的重点在于连续二字上，我们只需要向前找到第一个比当前数字大的位置就停止。那么我们只需要找到数字A其前面有多少个连续的并且比它小的数字个数a即可，这样，当我们后面出现一个数字B，当B>=A时，在B前面小于等于B的连续数字共有a + 1个；当B < A时，在B前面小于等于B的连续数字只有1个，那就是B自己。
思路是使用一个单调递减栈，这个栈里保存的是当前的价格向前可以找连续的多少天。注意这个栈里存放的内容是严格单调递减的，如果新来的数值大于了栈顶元素，那么就要把栈顶的元素给弹出去，直到当前元素小于栈顶才行。
这样做的好处就是，我们没必要保留较小的元素，只需要知道每个元素前面有几个比它小的数字就行了。因为我们在遍历的过程中，是在找比当前元素小的元素个数，栈顶保留的只有较大的元素和它前面出现的次数，那么就知道了前面比它小的元素个数。
如果按照题目的示例，每次next()函数调用之后，栈中的内容如下：
[(100, 1)]
[(100, 1), (80, 1)]
[(100, 1), (80, 1), (60, 1)]
[(100, 1), (80, 1), (70, 2)]
[(100, 1), (80, 1), (70, 2), (60, 1)]
[(100, 1), (80, 1), (75, 4)]
[(100, 1), (85, 6)]
每步操作的平均时间复杂度是O(1)，最坏的时间复杂度是O(n)，空间复杂度是O(1).
代码如下：
class StockSpanner(object):
def __init__(self):
self.a = []
def next(self, price):
"""
:type price: int
:rtype: int
"""
res = 1
while self.a and self.a[-1][0] <= price:
res += self.a.pop()[1]
self.a.append((price, res))
return res
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
参考资料：
https://leetcode.com/problems/online-stock-span/discuss/168311/C++JavaPython-O(1)
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发
28
4
0
所以我一直在寻找一种方法，当数量字段大于 0 时，将库存可用性更改回有库存。当您将数量设置为 0 并保存产品时，系统已经自动将库存可用性更改为缺货.当您将数量设置为大于 0 并保存产品时，我想要一种将
我对 Java 非常陌生，我试图理解为什么这段代码的 Magic 类的 main 方法的输出是“TT”。我们的教授说我们不必理解这个方法的含义，只要回答输出即可。 代码是这样的。 public cla
Magento 2:获取产品库存数量和其他库存信息 如何在magento 2中获取产品库存数量和信息 最佳答案 如果我们查看 StockItemRepository 类 get方法需要参数 $stoc
我有声明(或类似的) std::map &stocks; 贯穿我的代码。 Eclipse 不喜欢这样并产生“无效的模板参数”错误。 库存声明为: class Stock { public:
在 Admin Woocommerce 产品页面上，对于可变产品，在“变体”设置中，对于所有产品变体，我希望默认启用 Manage Stock 选项，并使用 Stock Quantity 选项设置为
我一直在学习向Gtk进行开发，并且在线上的大多数示例都建议使用Gtk.stock图标。但是，使用它会产生警告，表明它已被弃用，我找不到这些图标的替代品。 代码示例为: open_button:
已关闭。此问题不符合Stack Overflow guidelines 。目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是偏离主题的，因为
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题？ Update the question所以它是on-topic对于堆栈溢出。 9年前关闭。 Improve this que
在 GWT Stock Watch 教程中，它似乎每 4 秒轮询一次服务器以获取新数据。这是 GWT 的标准工作方式还是可以使用推送类型技术，以便在服务器上引发新事件时调用客户端代码？ 最佳答案 这是
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。 想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。 7年前关闭。 Improve thi
我似乎在我的系列数据散列中可以拥有的数据点数量受到某种限制。我正在像这样创建我的数据哈希: var data_hash = []; var limit = 1000; for(var i = 0; i
股票初始值为 1 流量为0.1 Stock1 初始值为 0。 当我运行模拟时，我意识到股票的值(value)低于 0(获得负值)。当 Stock 的值达到零时如何停止流动。 最佳答案 一个应该有一个非
我在程序中执行用户定义方法时遇到问题，如果有人能帮助我就好了 package Ex_9_2; public class TestStock { public static String price;
例如，当我想在普通消息应用程序中将图像附加到文本消息时，我会看到一个熟悉的系统对话框，其中显示相机、图库和其他图像内容提供程序。 我想在我自己的应用程序中使用它。我看到很多库允许用户在 Gallery
我正在开发自行车库存。我将Cycles cid,title, desc etc存储在CYCLE表中，并在另一个STOCK(sid,cid,qty)中存储库存。现在我知道自行车可以有多种颜色(黑色、红色
#include #include #include using namespace std; class Product { string title; string sirN
题目地址：https://leetcode.com/problems/online-stock-span/description/ 题目描述 Write a class StockSpanner
我需要将“ # in stock ”文本更改为“ # Deals left ”。 我将以下代码添加到 function.php 文件中，但这会删除实际数字。 add_filter( 'woocomme
我无法从 Alpha Vantage TIME_SERIES_DAILY、TIME_SERIES_DAILY_ADJUSTED 或 TIME_SERIES_INTRADAY 获取任何 NASDAQ 数
http://en.wikipedia.org/wiki/MetaStock 有人知道如何将 metastock 数据格式转换为 ASCII/CSV 格式吗？ 任何示例代码(c++/c#)都会有很大帮
我是一名优秀的程序员,十分优秀！