[leetcode/lintcode 題解] 算法面試高頻題詳解：股票價格跨度

描述

編寫一個 StockSpanner 類，它收集某些股票的每日報價，并傳回該股票當日價格的跨度。

今天股票價格的跨度被定義為股票價格小于或等于今天價格的最大連續日數（從今天開始往回數，包括今天）。

例如，如果未來7天股票的價格是 [100, 80, 60, 70, 60, 75, 85]，那麼股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

• 調用 StockSpanner.next(int price) 時，将有 1 <= price <= 10^5。
• 每個測試用例最多可以調用 10000 次 StockSpanner.next。
• 在所有測試用例中，最多調用 150000 次 StockSpanner.next。
• 此問題的總時間限制減少了 50%。

線上評測位址：

領扣題庫官網

樣例1
輸入：prices = [100,80,60,70,60,75,85]
輸出：[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。

注意 (例如) S.next(75) 傳回 4，因為截至今天的最後 4 個價格
(包括今天的價格 75) 小于或等于今天的價格。           

樣例2
輸入：prices = [50,80,80,70,90,75,85]
輸出：[1,2,3,1,5,1,2]
解釋：
首先，初始化 S = StockSpanner()，然後：
S.next(50) 被調用并傳回 1，
S.next(80) 被調用并傳回 2，
S.next(80) 被調用并傳回 3，
S.next(70) 被調用并傳回 1，
S.next(90) 被調用并傳回 5，
S.next(75) 被調用并傳回 1，
S.next(85) 被調用并傳回 2。           

解題思路

單調棧問題 題目中提到股票價格小于或等于今天價格的最大連續日數。 由于這是一個線上問題，是以我們必然是要将輸入的price給存儲起來，而且同時我們也需要保留這是第幾次輸入的資訊。 需要注意的是邊界問題，當我們輸入第一個price的時候，此時stack空。 是以這裡拿出來判斷特殊處理一下

源代碼

public class StockSpanner {
    public StockSpanner() {
        
    }
    
    /**
     * @param price: 
     * @return: int
     */
     
     Stack<int[]> stack = new Stack<>();
    public int next(int price) {
        // Write your code here.
        int res = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price)
            res += stack.pop()[1];
        stack.push(new int[]{price, res});
        return res;
    }
}           

更多題解參考：

九章官網solution