两种解法,一种是暴力(本题过不去,会超时),一种是单调栈
算法1 暴力枚举
两层循环,外层循环遍历一遍数组,内层循环以当前$a_i$为起点向前遍历一遍直到找到比$a_i$小的那个值再输出退出循环
采用flag变量作为标志判断一下找没找到比$a_i$小的值,没找到的话就输出-1
当然,本题采用暴力做法过不去,会超时
时间复杂度
$O(n^2)$
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int flag;
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
cout << "-1" << " ";
for (int i = 1; i < n; i++) {
for (int j = i - 1; j > -1; j--) {
if (a[i] > a[j]) {
cout << a[j] << " ";
flag = 1;
break;
}
}
if (flag == 0)cout << -1 << " ";
flag = 0;
}
return 0;
}
算法2 单调栈
与y总的一致,参考了高赞题解 AcWing 830. 单调栈–图解,详细注释
时间复杂度
<$O(n^2)$
C++ 代码
#include<iostream>
#include<stack>
using namespace std;
const int N = 1e5 + 10;
stack<int> stk;
int flag;
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) {
cin >> flag;
while (!stk.empty() && stk.top() >= flag)stk.pop(); // 如果栈顶元素大于当前待入栈元素,则出栈
if (!stk.empty())cout << stk.top() << " "; // 如果栈空,则没有比该元素小的值。
else cout << "-1" << " "; // 栈顶元素就是左侧第一个比它小的元素。
stk.push(flag);
}
return 0;
}