[[414650]]

對單調棧理解不透徹，當時沒想到。

其實單調棧題目的特征很明顯。

一般來講，單調棧題目需要就數學關系進行分析，比如：

• 我們需要尋找一個非凹子序列
• 即我們需要尋找兩個子序列，一個在左邊單調增，一個在右邊單調減，因此用兩個單調棧分別從左往右和從右往左預處理序列

非凹的序列應該只有這三種

單調棧有什么特性呢?我該怎么想到：「喔，這個問題可以用單調棧來解決呢?」我總結了一下：

• 遍歷到 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/