单调栈如何巧妙地应用于长尾词的解析？
- 内容介绍
- 文章标签
- 相关推荐
本文共计566个文字，预计阅读时间需要3分钟。
题目：给定一个长度为$N$的整数序列，输出每个数的左边第一个比它小的数，如果不存在则输出$-1$。
输入格式：第一行包含一个整数$N$，表示序列的长度。第二行包含$N$个整数，表示序列中的元素。
输出格式：输出$N$行，每行输出一个整数，表示对应位置上每个数的左边第一个比它小的数。
例如：输入：
54 5 2 3 1
输出：
-124
-15
题目
给定一个长度为 $N$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $−1$。
输入格式 第一行包含整数 $N$，表示数列长度。
第二行包含 $N$ 个整数，表示整数数列。
输出格式 共一行，包含 $N$ 个整数，其中第 $i$ 个数表示第 $i$ 个数的左边第一个比它小的数，如果不存在则输出 $−1$。
数据范围 $1≤N≤10^5$
$1≤数列中元素≤10^9$
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
思路
求解给定一个序列，求序列中的每一个数左边或右边第一个比他大或比他小的数在什么地方这类题目时可用单调栈来解决问题. 本题中, 对于每一个输入的数值, 在未插入前保证栈内数值单调递增, 栈顶元素即为该点左侧第一个小于的点, 不存在则输出 $-1$.
代码
#include <iostream>
#include <stack>
using namespace std;
stack <int> stk;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
while (!stk.empty() && stk.top() >= x) stk.pop(); // 保证栈内递增
if (stk.empty()) cout << "-1" << " ";
else cout << stk.top() << " ";
stk.push(x);
}
return 0;
}
本文共计566个文字，预计阅读时间需要3分钟。
题目：给定一个长度为$N$的整数序列，输出每个数的左边第一个比它小的数，如果不存在则输出$-1$。
输入格式：第一行包含一个整数$N$，表示序列的长度。第二行包含$N$个整数，表示序列中的元素。
输出格式：输出$N$行，每行输出一个整数，表示对应位置上每个数的左边第一个比它小的数。
例如：输入：
54 5 2 3 1
输出：
-124
-15
题目
给定一个长度为 $N$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $−1$。
输入格式 第一行包含整数 $N$，表示数列长度。
第二行包含 $N$ 个整数，表示整数数列。
输出格式 共一行，包含 $N$ 个整数，其中第 $i$ 个数表示第 $i$ 个数的左边第一个比它小的数，如果不存在则输出 $−1$。
数据范围 $1≤N≤10^5$
$1≤数列中元素≤10^9$
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
思路
求解给定一个序列，求序列中的每一个数左边或右边第一个比他大或比他小的数在什么地方这类题目时可用单调栈来解决问题. 本题中, 对于每一个输入的数值, 在未插入前保证栈内数值单调递增, 栈顶元素即为该点左侧第一个小于的点, 不存在则输出 $-1$.
代码
#include <iostream>
#include <stack>
using namespace std;
stack <int> stk;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
while (!stk.empty() && stk.top() >= x) stk.pop(); // 保证栈内递增
if (stk.empty()) cout << "-1" << " ";
else cout << stk.top() << " ";
stk.push(x);
}
return 0;
}