? ? ? ? 單調棧作為一種數據結構在求解類遞增、遞減方面的題目中有較為廣泛的應用，在以往的leetcode中所見到的相關單調棧的題目均為單一元素，今天刷到901題目時，想到了將數組元素作為單調棧中元素的方法進行求解。

題目鏈接及描述

901. 股票價格跨度 - 力扣（LeetCode）

題目分析? ? ? ??

????????做這到題目首先想到的是使用一個數組將其元素依次存起來，隨后將其轉換為一個數組相關的題目，但由于數組需要實現開辟好空間，不太好確定，考慮使用List來實現，當調用next方法就將其存儲到List集合中。此時List集合中的元素類型為一個一維數組，并且數組大小為2，第一個元素為price，第二個元素為price對應的價格跨度。

? ? ? ? 將示例代碼構造為階梯圖如下所示：

? ? ? ? 最左邊元素為Integer.MAX_VALUE，添加此元素，可以減少棧的非空判斷。減少代碼復雜度。

? ? ? ? 根據題目：當日股票價格的?跨度?被定義為股票價格小于或等于今天價格的最大連續日數。故單調棧中存儲的元素應為遞減的，每當調用依次next方法，需要不斷循環彈出當前棧頂小于當前價格price的元素，最后當前價格price對應的下標 - 棧頂元素對應的下標即為所求結果。當遍歷到75時當前棧如下所示：

? ? ? ? 遍歷到元素75，此時棧中的情況：上圖中下標2和下標4對應的藍色柱形條表示已經出棧的元素。

? ? ? ? 循環遍歷當前棧頂元素與元素75進行比較，最終下標3對應的元素70出棧，則75對應的結果為5 - 1 = 4。

代碼編寫：

class StockSpanner {public Deque<int[]> mst;public int idx;public StockSpanner() {this.mst = new ArrayDeque<>();this.idx = 0;mst.addLast(new int[]{Integer.MAX_VALUE, -1});}public int next(int price) {while(!mst.isEmpty() && price >= mst.peekLast()[0]){mst.pollLast();}int ans = idx - mst.peekLast()[1];mst.addLast(new int[]{price, idx++});return ans;}
}

? ? ? ??