单调栈

单调栈实现

单调栈是一种常用的数据结构，用于解决一类特殊的栈问题。本文将介绍如何使用C++实现单调栈。

问题描述

给定一个长度为 n 的数组，找出每个元素左边第一个比它小的数。如果不存在这样的元素，则输出 -1。

代码实现

以下是一个实现单调栈的完整C++代码示例：

#include <iostream>
using namespace std;

const int N  = 100010;
int st[N], tt;

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

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

5
2 4 3 1 5

输出：

-1 2 2 -1 1

示例 2

输入：

6
1 2 3 4 5 6

输出：

-1 1 2 3 4 5

示例 3

输入：

6
6 5 4 3 2 1

输出：

-1 -1 -1 -1 -1 -1

代码说明

初始化单调栈：

• 定义数组 st 存储栈中的元素，tt 为栈顶指针。

处理输入数据：

• 读取输入的整数 n，表示数组的长度。
• 遍历输入的每个元素 x，维护一个单调递增的栈，输出每个元素左边第一个小于它的元素。

主函数逻辑：

• 初始化栈，读取输入数据，并按照单调栈的规则处理和输出结果。