文章目錄
- 題目
- 解題思路
- Python實現(xiàn)
題目
編寫一個 StockSpanner 類，它收集某些股票的每日報價，并返回該股票當日價格的跨度。
今天股票價格的跨度被定義為股票價格小于或等于今天價格的最大連續(xù)日數(shù)（從今天開始往回數(shù)，包括今天）。
例如，如果未來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。
解題思路
因為是當前天數(shù)往前數(shù)價格
連續(xù)下降的天數(shù)。分為兩種情況：1. 如果當前價格在前幾天（連續(xù)小于等于的情況下）出現(xiàn)過，則直接將當前最大天數(shù)加一即為新價格的最大連續(xù)天數(shù)。2. 如果沒有出現(xiàn)過則比較大小看是否需要繼續(xù)遍歷，如果需要，則跳轉到前一個最大連續(xù)天數(shù)的位置再進行遍歷，不需要重復比較。
不需要重復遍歷很重要，因為有一個測試樣例是有大量的重復，此時，對于重復的數(shù)據(jù)我們只需要知道前一個重復數(shù)據(jù)的最大活躍天數(shù)并加一即可。
Python實現(xiàn)
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)
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
