審題：

本題是單調棧的模板題

補充：單調棧

單調棧中的數據始終保持單調遞增或單調遞減

使用情景：給定一個數組，要求尋找

1.某個數左側，離他最近且值大于他的數

2.某個數左側，離他最近且值小于他的數

3.某個數右側，離他最近且值大于他的數

4.某個數右側，離他最近且值小于他的數

我們先分析情況1：

由于搜索范圍是數的左側，所以我們的遍歷順序是從左往右遍歷，要求尋找的數是大于他的，所以我們的棧是單調遞減的

代碼邏輯分析：

（1）棧頂數據的值小于等于當前數據：說明當前索引位置不存在左側大于他的數，且當前棧頂數據也不會成為后續的其他數據的要求數（假設其可以成為后續數據的要求數，那么當前遍歷到的數據會比他更符合要求，故不可能）

于是我們需要循環進行棧彈出操作，直到棧頂數據值大于當前數據，或棧為空

（2）棧頂數據的值大于當前數據/棧為空：說明找到了要求數，更新ret數組

（3）將當前數據插入到棧中

接下來看看情況2：

搜索范圍沒變，所以我們還是從左往右遍歷，要求尋找的數是小于他的，所以我們采用單調遞增的棧

代碼邏輯分析：

我們只需要改變一個地方，將情況1代碼中的小于等于換成大于等于，大于換成小于即可

然后看看情況3和4：

他們和情況1與2最大的區別就是搜索范圍，變為了右側，所以我們逆著搜索，也就是從右往左搜索

---

然后我們看看這題屬于情況3，所以我們直接寫代碼即可

#include<iostream>
#include<stack>
using namespace std;
int n;
const int N = 3e6 + 10;
int a[N],b[N];
void func()//找到該數右側距離他最近的且比他大的元素的下標
{stack<int> s;for (int i = n; i >= 1; i--)//從右往左遍歷{//建立單調遞減棧while (s.size() && a[s.top()] <= a[i]){s.pop();}//記錄對應元素所拿到的元素下標if (s.size()) b[i] = s.top();else b[i] = 0;//插入下標到棧s.push(i);}
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}func();for (int i = 1; i <= n; i++){cout << b[i] << " ";}return 0;
}

注意：

1.棧中存儲的是數組對應的下標

P5788 【模板】單調棧 - 洛谷