刷力扣時，遇到關鍵詞：下一個更大/小的數這類題目時，往往會採用單調棧的解法，如每日温度

刷題最常見的問題就是，看到題解，感覺很精妙，但下次遇到一模一樣的題目時，往往知道思路，但寫不出代碼，有或者遇到類似的變體題目時，不會往這方面想。這兩種情況在之前的文章(數據結構算法小結)中提到過，分別有兩方面的原因：

1. 對工具（如單調棧知識點）的特性（適用範圍）不明朗
2. 對工具的原理沒有真正的理解

初學單調棧最容易搞錯的一點是，獲取下一個更大的數，往往需要用下降棧，下一個更小的數卻要用上升棧。

本篇將會從單調棧的原理特性入手，分析單調棧原理和用法，並給出固定的方法模板。

單調棧場景分析

如果一上手就結合問題講單調棧怎麼用，注意力往往在解法上，而容易忽視單調棧的特性，這裏先以單調上升棧為例，分析進出棧的特性：

假設原數組為[5,1,6,2,0,7],從左向右入棧，維護一個單調上升棧，過程如圖所示：

可以發現，單調上升棧更適合維護下一個更小值的數組，若讓其維護下一個更大值的數組，過程中便會發現，無法對已出棧的數據進行比較，如果再加一個棧保存出棧數據，計算的複雜度又會變成O(n^2),變沒有達到優化的效果。

小結

根據上面例子做個小結：

• 單調棧適用問題

  • 獲取某個值的下一個更大/更小值

• 上升棧還是下降棧

  • 獲取下一個更小值：維護一個上升棧
  • 獲取下一個更大值：維護一個下降棧

• 什麼時候往下一個更大/更小數組中塞入值：

  • 數據出棧時

單調棧問題的模板

根據上面的例子，不難總結出單調棧問題的模板：

// 模板:
const fillArr = (arr, isNextLowerArr) => {
  const stack = [];
  const getTop = () => stack[stack.length - 1];
  // isNextLowerArr為true -> 維護[下一個更小]數組 -> 上升棧
  const validFunc = isNextLowerArr
      ? ((topVal, compareVal) => compareVal >= topVal)
      : ((topVal, compareVal) => compareVal <= topVal)
  const addData = (data) => {
      let top = getTop();
      // stack不為空，且頂部值不符合上升/下降規則時，頂部出棧，並填充數組
      while(top && !validFunc(top.val, data.val)) {
          arr[top.index] = data;
          stack.pop();
          top =  getTop();
      }
      stack.push(data);
  }
  addData.getStack = ()=> stack;
  return addData;
}
// test:
const testArr = [5,1,6,2,0,7];
const nextLowerArr = Array(testArr.length).fill(null);
const addDataToIncreaseStack = fillArr(nextLowerArr, true);
// 同理，獲取下一個更大數組，獲取添加數據函數就是fillArr(nextUpperArr, false)
testArr.forEach((val, index) => {
    const data = {val, index};
    addDataToIncreaseStack(data);
    console.log("stack:", [...addDataToIncreaseStack.getStack()]);
    console.log("nextLowerArr:", [...nextLowerArr]);
})

後話

明確模板之後，可自行嘗試每日温度這一題。

很多時候，比起掌握方法，更進一步總結出模板無疑更有效率，下次遇到同樣問題的時候，只需要將複雜問題拆解成多個子問題，分別套模板就行，就和做項目時調用第三方庫一樣；如果只是感性的掌握解法，解決問題時一點失誤都會導致結果出錯。