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