1. 題目

編寫一個(gè) StockSpanner 類，它收集某些股票的每日?qǐng)?bào)價(jià)，并返回該股票當(dāng)日價(jià)格的跨度。

今天股票價(jià)格的跨度被定義為股票價(jià)格小于或等于今天價(jià)格的最大連續(xù)日數(shù)（從今天開始往回?cái)?shù)，包括今天）。

例如，如果未來(lái)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。注意 (例如) S.next(75) 返回 4，因?yàn)榻刂两裉斓淖詈?4 個(gè)價(jià)格 (包括今天的價(jià)格 75) 小于或等于今天的價(jià)格。提示： 調(diào)用 StockSpanner.next(int price) 時(shí)，將有 1 <= price <= 10^5。 每個(gè)測(cè)試用例最多可以調(diào)用 10000 次 StockSpanner.next。 在所有測(cè)試用例中，最多調(diào)用 150000 次 StockSpanner.next。 此問題的總時(shí)間限制減少了 50%。

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/online-stock-span
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 單調(diào)棧，棧內(nèi)存儲(chǔ)《數(shù)值，小于等于其的個(gè)數(shù)》
• 如果當(dāng)前 price >= 棧頂，把計(jì)數(shù)累積，彈棧，直到遇到比當(dāng)前大的，停止
  

class StockSpanner {stack<pair<int,int>> stk;int days; public:StockSpanner() {}int next(int price) {days = 1;while(!stk.empty() && price >= stk.top().first){days += stk.top().second;//個(gè)數(shù)合并stk.pop();//刪除小的}stk.push({price,days});return days;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 901. 股票价格跨度（单调栈）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。