用 單調棧 來解 最近幾日股價的高點 Online Stock Span_Leetcode #901精選75題

m. null on Unsplash

題目敘述

題目會給我們一個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~十萬之間。

• At most 10^4 calls will be made to next.

動態測試時，最多有一萬次next() function呼叫。

演算法 Monotone Stack 單調棧

其實這題和前一題 每日溫度變化 Daily Temperatures 有異曲同工之妙，前一題是找之後比較大的值(之後比較溫暖的日子)，這題是找能覆蓋前k天以來的數值(相當於說，今天的股價，是k天以來的最高點)，背後的本值都時一樣的，都是盡可能的擴張區間，直到條件滿足為止。

維護一個遞減單調棧，每次呼叫next() function推入今天股價時，把前面比較小的價格都pop出來，並且趁機計算能夠覆蓋的天數k值，最後再把k值回傳即可。

範例 + 示意圖