單調(diào)棧一點(diǎn)小心得 | 用最簡單的動(dòng)圖和例題解釋一下
對(duì)單調(diào)棧理解不透徹，當(dāng)時(shí)沒想到。
其實(shí)單調(diào)棧題目的特征很明顯。
一般來講，單調(diào)棧題目需要就數(shù)學(xué)關(guān)系進(jìn)行分析，比如：
- 我們需要尋找一個(gè)非凹子序列
- 即我們需要尋找兩個(gè)子序列，一個(gè)在左邊單調(diào)增，一個(gè)在右邊單調(diào)減，因此用兩個(gè)單調(diào)棧分別從左往右和從右往左預(yù)處理序列
非凹的序列應(yīng)該只有這三種
單調(diào)棧有什么特性呢?我該怎么想到：「喔，這個(gè)問題可以用單調(diào)棧來解決呢?」我總結(jié)了一下：
- 遍歷到 i 時(shí)，總會(huì)把 i 推入棧，總會(huì)保證棧頂?shù)綏５资墙敌虻?。因此在?i 入棧前，從棧頂開始，把比 i 高(大于等于)的都 pop 出來。
即，單調(diào)棧是一種預(yù)處理技術(shù)。用 的時(shí)間處理一個(gè)長度為 的序列，會(huì)得到這 個(gè)元素的最相鄰的比自己小的元素 / 比自己大的元素 / 以該元素結(jié)尾的遞增或遞減子序列長度等。
這非常 amazing ，按理說，想要得到 個(gè)信息，起碼要用 或者 的時(shí)間吧。
搞個(gè)動(dòng)圖和經(jīng)典例題解釋一下。
我們有一個(gè)長度為 5 的序列：3 4 2 7 5 ，我們希望找到每一個(gè)數(shù)左邊的第一個(gè)比自己小的數(shù)。我們知道分別是：沒有 3 沒有 2 2 。如何設(shè)計(jì)一個(gè)算法讓計(jì)算機(jī)自動(dòng)找到這些數(shù)呢?見下面的動(dòng)圖。
因此咱們可以總結(jié)出其性質(zhì)如下。
例題：尋找左邊最近的比自己小的數(shù)
來源：AcWing在線題庫[3]
- 給定一個(gè)長度為 N 的整數(shù)數(shù)列，輸出每個(gè)數(shù)左邊第一個(gè)比它小的數(shù)，如果不存在則輸出 −1。
輸入格式
- 第一行包含整數(shù) N，表示數(shù)列長度。
- 第二行包含 N 個(gè)整數(shù)，表示整數(shù)數(shù)列。
輸出格式
- 共一行，包含 N 個(gè)整數(shù)，其中第 i 個(gè)數(shù)表示第 i 個(gè)數(shù)的左邊第一個(gè)比它小的數(shù)，如果不存在則輸出 −1。
分析：
- 首先想到兩層循環(huán)，暴力做法;接下來想哪里可以優(yōu)化(類似雙指針的思路)
- 注意一個(gè)性質(zhì)，如果 i < j ，且 a[i] >= a[j] ，那么我們之后都沒必要管 i 了，因?yàn)?j 比 i 更加靠右，且值更小;后面的數(shù)向左搜索的過程中，碰到 j 覺得不行(還沒 a[j] 大呢)，碰到 i 更不會(huì)覺得行了(更不會(huì)有 a[i] 大)
- 用單調(diào)棧實(shí)現(xiàn)
- #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/
