單調棧一點小心得 | 用最簡單的動圖和例題解釋一下
本文轉載自微信公眾號「Piper蛋窩」，作者Piper蛋 。轉載本文請聯系Piper蛋窩公眾號。
上上周 力扣雙周賽 T4[1] 和 Acwing 第 9 場周賽最后一題[2] 的考點竟然都是單調棧。
對單調棧理解不透徹，當時沒想到。
其實單調棧題目的特征很明顯。
一般來講，單調棧題目需要就數學關系進行分析，比如：
- 我們需要尋找一個非凹子序列
- 即我們需要尋找兩個子序列，一個在左邊單調增，一個在右邊單調減，因此用兩個單調棧分別從左往右和從右往左預處理序列
非凹的序列應該只有這三種
單調棧有什么特性呢?我該怎么想到：「喔，這個問題可以用單調棧來解決呢?」我總結了一下：
遍歷到 i 時，總會把 i 推入棧，總會保證棧頂到棧底是降序的。因此在把 i 入棧前，從棧頂開始，把比 i 高(大于等于)的都 pop 出來。
即，單調棧是一種預處理技術。用 的時間處理一個長度為 的序列，會得到這 個元素的最相鄰的比自己小的元素 / 比自己大的元素 / 以該元素結尾的遞增或遞減子序列長度等。
這非常 amazing ，按理說，想要得到 個信息，起碼要用 或者 的時間吧。
搞個動圖和經典例題解釋一下。
我們有一個長度為 5 的序列：3 4 2 7 5 ，我們希望找到每一個數左邊的第一個比自己小的數。我們知道分別是：沒有 3 沒有 2 2 。如何設計一個算法讓計算機自動找到這些數呢?見下面的動圖。
因此咱們可以總結出其性質如下。
例題：尋找左邊最近的比自己小的數
來源：AcWing在線題庫[3]
- 給定一個長度為 N 的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出 ?1。
輸入格式
- 第一行包含整數 N，表示數列長度。
- 第二行包含 N 個整數，表示整數數列。
輸出格式
- 共一行，包含 N 個整數，其中第 i 個數表示第 i 個數的左邊第一個比它小的數，如果不存在則輸出 ?1。
分析：
- 首先想到兩層循環，暴力做法;接下來想哪里可以優化(類似雙指針的思路)
- 注意一個性質，如果 i < j ，且 a[i] >= a[j] ，那么我們之后都沒必要管 i 了，因為 j 比 i 更加靠右，且值更小;后面的數向左搜索的過程中，碰到 j 覺得不行(還沒 a[j] 大呢)，碰到 i 更不會覺得行了(更不會有 a[i] 大)
- 用單調棧實現
- #include <iostream>
- using namespace std;
- const int N = 1e5 + 10;
- int stk[N], tt;
- int main()
- {
- int n, x;
- cin >> n;
- for (int i = 0; i < n; i ++)
- {
- cin >> x;
- while (tt && stk[tt] >= x) tt --;
- if (tt) cout << stk[tt] << " ";
- else cout << -1 << " ";
- stk[++ tt] = x;
- }
- return 0;
- }
參考資料
[1]力扣雙周賽 T4: https://leetcode-cn.com/problems/number-of-visible-people-in-a-queue/
[2]Acwing 第 9 場周賽最后一題: https://www.acwing.com/problem/content/3783/
[3]AcWing在線題庫: https://www.acwing.com/problem/content/832/
