【19. 单调栈】

单调栈

用途：主要找到每个数左边离他最近的且比它小的数在什么地方(或者找到每个数右边离他最近的且比它大的数在什么地方)

题目

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围

1≤ N ≤ 105
1≤ 数列中元素 ≤ 109

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

方法一：暴力解法

for (int i = 0; i < n; i ++)
    for (int j = i - 1; j >= 0; j --)
        if (a[i] > a[j])
        {
            cout << a[j] << endl;
            break;
        }

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)  cin >> q[i];
    
    for (int i = 0; i < n; i ++)
    {
        int j = i - 1;
        for (; j >= 0; j --)
        {
            if (q[j] < q[i])
            {
                cout << q[j]<<" ";
                break;
            }
             
        }
        if (j < 0)
       {
         cout << "-1" <<" ";
       }
    }
    return 0;
}

方法二：优化

• 用栈存储 i 左边的元素
• 如果 ax >= ay,并且x < y那么ax永远不会输出，就直接可以删除。(只要有这种逆序的关系，前面的数就会被删掉，此时剩下的序列就是单调序列了)

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int stk[N], tt;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) tt -- ;
        if (tt) cout << stk[tt] << " ";
        else cout << "-1" << " ";
        stk[ ++ tt] = x;
        //cout << tt << endl;;
    }
    return 0;
}