單調棧

• 單調棧：是一種容器，類似于大小堆，一維數組：
  • 單調遞增棧：從棧低到棧頂是遞增的，【記錄的是已遍歷更大的數，求的是右邊第一個更小的數】，獲取當前元素，左邊大于的第一個數，右邊小于的第一個數；
  • 單調遞減棧：從棧底到棧頂是遞減的，【記錄的是已遍歷更小的數，求的是右邊更大的數】，因此當前元素能夠獲取，左邊小于的第一個數，右邊大于的第一個數；
  • 判斷邏輯：
    • 大于棧頂，
    • 等于棧頂：關鍵點的細節，判斷條件是否是需要滿足嚴格單調關系；
    • 小于棧頂，
• 經典題型：
  • 每日溫度：單調遞減棧，其次，從數據層考察，兩個數組，循環數組等；
  • 接雨水：嚴格單調遞減的棧，
    • 考察點：對于當前元素等于棧頂時，置換不知換對該位置的雨水容量不影響，但是影響以它為高的容積寬度【w = i - left - 1】，所以應該更新棧頂元素；
  • 柱狀圖中的最大矩形：嚴格單調遞增的棧，
    • 有一個迭代思想，由中間的棧頂求面積，然后逐步向下迭代，求最大值；