算法
(不太暴力枚举) $O(n^2)$
可以找到规律:
1 res[0]= -1
2 如果q[i]>q[i-1] 那么res[i] 就是res[i-1]和q[i-1]的最大值 res[i-1] 是前i-2 个数符合条件
3 否则 就从后往前找第一个比q[i]小的数。 也是只需要比较res[j]和q[i]的 大小即可
最坏情况下是 O(n^2)
时间复杂度
C++ 代码
/*
单调栈
找到序列中某一个数 某一边 离他最近的一个最大/最小的数
*/
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], res[N];
int main()
{
scanf("%d", &n);
//限制条件
if (n <= 1)
return -1;
for (int i = 0; i < n; i++)
{
scanf("%d", &q[i]);
}
res[0] = -1;
for (int i = 1; i < n; i++)
{
if (q[i] > q[i - 1])
{
res[i] = max(q[i - 1], res[i - 1]);
}
else
{
if (q[i] <= res[i - 1])
{
//从后往前,找到res中第一个比q[i]小的数 最坏情况下要整个遍历
for (int j = i - 1; j >= 0; j--)
{
if (q[i] > res[j])
{
res[i] = res[j];
break;
}
}
}
else
{
res[i] = res[i - 1];
}
}
}
for (int i = 0; i < n; i++)
{
printf("%d ", res[i]);
}
return 0;
}