【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 大的数