①寻找每个数左边第一个比它小的数

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
输入样例： 3 4 2 7 5
输出样例： -1 3 -1 2 2

从左到右遍历，用单调递增（栈底到栈顶）栈。让每次入栈前（如果当前元素要入的话）栈顶元素都是左边第一个比当前数小的数。

#include <bits/stdc++.h>
using namespace std;

int n;
stack<int> st;

int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int x;
        scanf("%d", &x);
        
        //单调递增栈（从栈底到栈顶）
        //每次入栈前（如果要入的话），栈顶都是左边第一个比当前数小的数，则单调递增
        while (!st.empty() && x <= st.top()) st.pop();
        if (!st.empty()) printf("%d ", st.top());
        else printf("-1 ");
        st.push(x); //如果当前数大于栈顶则入栈。记得入栈！！
    }
    return 0;
}

②寻找每个数左边第一个比它大的数

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
输入样例： 3 4 2 7 5
输出样例： -1 -1 4 -1 7

从左到右遍历，用单调递减栈。

#include <bits/stdc++.h>
using namespace std;

int n;
stack<int> st;

int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int x;
        scanf("%d", &x);
        
        while (!st.empty() && x >= st.top()) st.pop();
        if (!st.empty()) printf("%d ", st.top());
        else printf("-1 ");
        st.push(x);
    }
    return 0;
}

③寻找每个数右边第一个比它大的数

给定一个长度为 N 的整数数列，输出每个数右边第一个比它大的数，如果不存在则输出 −1。
输入样例： 3 4 2 7 5
输出样例： 4 7 7 -1 -1

从左到右遍历，用单调递减栈。栈里存储的数是都还没找到下一个更大的数，一旦找到了一个比栈顶大的数，立刻更新栈顶元素，同时把栈顶元素出栈。因为出栈时是倒序，不能直接输出答案，需要用个数组存储。
这里的栈存储的是元素的下标

#include <bits/stdc++.h>
using namespace std;

const int N  =100010;
int n;
stack<int> st; //存储的是当前元素的下标
int a[N], res[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (int i = 0; i < n; i++)
    {
        int x = a[i];
        
        while (!st.empty() && x > a[st.top()])
        {
            res[st.top()] = x;
            st.pop();
        }
        st.push(i);
    }
    
    for (int i = 0; i < n; i++)
    {
        if (res[i] == 0) printf("-1 ");
        else printf("%d ", res[i]);
    }
    return 0;
}

④寻找每个数右边第一个比它小的数

给定一个长度为 N 的整数数列，输出每个数右边第一个比它小的数，如果不存在则输出 −1。
输入样例： 3 4 2 7 5
输出样例： 2 2 -1 5 -1

从左到右遍历，用单调递增栈。栈里存储的数是都还没找到下一个更小的数，一旦找到了一个比栈顶小的数，立刻更新栈顶元素，同时把栈顶元素出栈。因为出栈时是倒序，不能直接输出答案，需要用个数组存储。
这里的栈存储的是元素的下标

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N], res[N];
stack<int> st;
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (int i = 0; i < n; i++)
    {
        int x = a[i];
        while (!st.empty() && x < a[st.top()])
        {
            res[st.top()] = x;
            st.pop();
        }
        st.push(i);
    }
    
    for (int i = 0; i < n; i++)
    {
        if (res[i] == 0) printf("-1 ");
        else printf("%d ", res[i]);
    }
    return 0;
}