单调栈

(单调栈模板题)
题目描述
给定一个长度为n的整数数组a，你需要求出每个元素的左边离它最近且比它小的元素。

输入描述
第一行：一个整数n(1≤n≤2×10^5)
第二行：n个整数，表示整数数组a.(1≤a≤10^9)

输出描述
共一行，n个整数，表示每个元素的左边第一个比它小的元素，若不存在则为−1。

输入样例1
5
7 8 5 6 7
输出样例1
-1 7 -1 5 6

我们可以使用STL中的stack实现
思路主要为将数组中的数值于栈中的数值进行对比，但栈中的数组比数组中的值大时，我们需要舍弃栈中的数，否则将数组中的值压入栈中
代码示例:

#include<iostream>
#include<stack>
using namespace std;
const int N = 2e5;
int a[N], b[N];
int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];

    stack<int>q;

    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.top() >= a[i])q.pop();
        if (q.empty())b[i] = -1;
        else b[i] = q.top();
        q.push(a[i]);
    }
    for (int i = 1; i <= n; i++)cout << b[i] << " ";
    return 0;
}

使用stack是一种选择，但是更推荐使用数组模拟来实现单调栈，因为数组能进行更多操作，对于题目的适应与灵活度更高。但是因为数组空间固定要注意数组栈的溢出问题。
下面给出数组实现的代码:

#include<iostream>
using namespace std;
const int N = 2e5;
int a[N], b[N], stk[N], top;
int main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];

    for (int i = 1; i <= n; i++) {
        while (top && a[stk[top]] >= a[i])top--;
        if (top)b[i] = a[stk[top]];
        else b[i] = -1;
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++)cout << b[i] << " ";
    return 0;
}