单调栈

单调栈的用途：在面对类似“求数列中每个元素的左边第一个小于他的数”的问题时，将时间复杂度为o(n方)的暴力解法优化为o(n)。
具体操作：以本题为例，在遍历数组元素时，对其进行判断，若栈顶元素小于等于当前元素，栈顶元素出栈，否则保持不变，这样栈内元素一定是单调递减的，然后判断栈内元素是否为空，若为空则说明没有比当前元素更大的数，输出0，否则输出栈顶元素。
本体收获1.从数组末尾开始反向单调栈。
2.用一个数组来存储下标，适合需要输出对应下标的题目。
C++代码

#include<stdio.h>
using namespace std;

const int N = 1e5 + 10;
int s[N],stk[N],ans[N];

int main()
{
    int n;
    int tt = 0;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)  scanf("%d",&s[i]);
    for(int i = n;i >= 1;i--)
    {
        while(tt!=0&&(s[stk[tt]]) <= s[i])  tt--;
        if(tt == 0)  ans[i] = 0;
        else ans[i] = stk[tt];
        stk[++tt] = i;
    }
    for(int i = 1;i <= n;i++) printf("%d\n",ans[i]);
    return 0;
}