iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
自我挑戰組

快樂社畜路:畢業後的後端開發求職準備系列 第 13

【LeetCode】Monotonic Stack

monotonic :單調,遞增或遞減

這是一個看起來很簡單的資料結構,
擁有 O(N) time complexity 的優秀特性,
但要能實際應用在問題裡卻不是很容易,
如果是用 heap 的題目,可以思考是否可以轉為使用 monotonic stack。

Time Complexity: O(N)

優點:linear time complexity
所有的元素最多只會進去一次,也最多只會出去一次。

性質 / 題型特徵

  1. Monotonic

  2. 元素 push 上 stack 前,會把破壞此 stack 單調性質(遞增或遞減)的元素移除。(LIFO)

  3. 可以找到目前元素向看(for all i < current_i)第一個比他小 / 大的元素

    • 往左看 就是 「已遍歷」、「目前為止」的感覺
    • 已遍歷中「最靠近」目前元素 and 符合某條件的元素
  4. 可以找到 目前為止最大的數

    • 「往左看比目前元素大 and 按序(遞減)排列」元素們
    • 往左看比目前元素大
      -> 得到比現元素大的已遍歷元素 or 現元素(代表沒有比較大的數)
      -> 得到 目前為止最大的數
    • 照順序遞減排列 -> 不怕第一大被刪除,我還知道第二大是誰。
    • [[239. Sliding Window Maximum]]
  5. 某些元素因為不符合和現元素相比的某個條件,在未來不會被用到了,可被捨棄。

  6. 某些元素被捨棄時,可能是答案。[[1944. Number of Visible People in a Queue]]

遞增: 找第一個左小

  • 找到 左邊第一個比目前元素小 的元素。

一個遞增的 monotonic stack,新增 a 進去,top 為頂元素。

  1. a > top,可以直接 push
    此時因為 monotonic,top 為 a 左邊第一個比 a 小的數
  2. a < top,為了維持 monotonic,要 pop 直到以下兩種情形才能 push a:
    1. pop 到 a > top
    2. stack empty
  • 若 pop 到 a > top,就是回 去 step 1. 的情形。
  • 若 stack 先空掉,則對 a 來說左邊沒有比較小的數

對這些被 pop 的元素來說,a 是在他們右側第一個比他們小的元素

遞減: 找第一個左大

  • 找到 左邊第一個比目前元素大 的元素。
  1. a < top,合法直接放
    top 為 a 左邊第一個比 a 大的數

上一篇
【LeetCode】Binary Search
下一篇
【LeetCode】DFS
系列文
快樂社畜路:畢業後的後端開發求職準備30

尚未有邦友留言

立即登入留言