文章目录
- 题目
- 解题思路
- Python实现
题目
编写一个 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。
解题思路
因为是当前天数往前数价格
连续下降的天数。分为两种情况：1. 如果当前价格在前几天（连续小于等于的情况下）出现过，则直接将当前最大天数加一即为新价格的最大连续天数。2. 如果没有出现过则比较大小看是否需要继续遍历，如果需要，则跳转到前一个最大连续天数的位置再进行遍历，不需要重复比较。
不需要重复遍历很重要，因为有一个测试样例是有大量的重复，此时，对于重复的数据我们只需要知道前一个重复数据的最大活跃天数并加一即可。
Python实现
class
StockSpanner
:
def
__init__
(
self
)
:
self
.
stock
=
[
]
self
.
ans
=
[
]
def
next
(
self
,
price
:
int
)
-
>
int
:
res
=
1
if
len
(
self
.
stock
)
==
0
:
self
.
ans
.
append
(
res
)
self
.
stock
.
append
(
price
)
else
:
i
=
len
(
self
.
stock
)
-
1
while
(
i
>=
0
)
and
(
price
>=
self
.
stock
[
i
]
)
:
res
+=
self
.
ans
[
i
]
i
-=
self
.
ans
[
i
]
self
.
ans
.
append
(
res
)
self
.
stock
.
append
(
price
)
return
res
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
