当前位置：首页 > ops >正文

【AcWing 830题解】单调栈

ops 2025/7/27 19:22:53

AcWing 830. 单调栈
【题目描述】
在这里插入图片描述
在查看解析之前，先给自己一点时间思考哦！
天津之眼
【题解】
题目要求给定一个整数序列，对于每个元素，输出其左侧第一个比它小的元素。如果不存在这样的元素，则输出-1。我们需要通过遍历数组来寻找每个元素的左侧第一个比它小的元素。为了解决这个问题，我们可以利用单调栈的方法。

1.单调栈的核心思想是栈中的元素是单调的，在这里我们可以让栈保持递减的顺序。具体来说，对于每个新的元素，我们将其与栈顶的元素进行比较，直到栈顶的元素小于当前元素时，当前元素的左侧第一个小于它的元素即为栈顶的元素。
2.如果栈为空，则说明当前元素左侧没有比它小的元素，此时输出 -1。
3.依次处理所有元素，最终得到每个元素左侧第一个比它小的元素。
【参考代码】

#include <iostream>
using namespace std;const int N = 1e5 + 10;  
int n, stk[N];  // stk数组用作栈，n是数组的长度int main() {cin >> n;  int tt = 0;  // 栈的指针，从栈底开始while (n--) {  int x;cin >> x;  // 当栈不为空且栈顶元素大于等于当前元素时，弹出栈顶元素while (tt && stk[tt] >= x)  // 如果栈顶大于当前元素，则弹出栈顶tt--;  // 出栈，栈指针减小if (!tt)  // 如果栈为空，说明左侧没有比当前元素小的数cout << "-1 ";  // 输出 -1else  // 否则输出栈顶的元素cout << stk[tt] << " ";  // 输出栈顶元素，即左侧第一个比当前元素小的元素stk[++tt] = x;  // 当前元素压入栈中，栈指针加1}return 0;  
}