題目會給我們一個StockSpanner類別,
還有對應的建構子和function: int next( int price)介面。
next(int price)呼叫的時後回傳入當天的股票價格,要求我們計算price這個價格是過去k天以來的最高價,返回k值。
舉例來說:
若股價分別是[70, 50, 60]
則分別回傳1, 1, 2
70是過去一天以來{70}的最高價
50是過去一天以來{50}的最高價
60是過去兩天以來{50, 60}的最高價
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
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85); // return 6
Constraints:
1 <= price <= 10^5
參數price介於1~十萬之間。
10^4
calls will be made to next
.動態測試時,最多有一萬次next() function呼叫。
其實這題和前一題 每日溫度變化 Daily Temperatures 有異曲同工之妙,前一題是找之後比較大的值(之後比較溫暖的日子),這題是找能覆蓋前k天以來的數值(相當於說,今天的股價,是k天以來的最高點),背後的本值都時一樣的,都是盡可能的擴張區間,直到條件滿足為止。
維護一個遞減單調棧,每次呼叫next() function推入今天股價時,把前面比較小的價格都pop出來,並且趁機計算能夠覆蓋的天數k值,最後再把k值回傳即可。