题目描述
Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.
输入
The first input line has an integer n: the size of the array.
The second line has n integers x1,x2,...,xn: the array values.
Constraints
1 ≤ n ≤
1 ≤ xi ≤
输出
Print n integers: for each array position the nearest position with a smaller value. If there is no such position, print 0.
样例输入
8
2 5 1 4 8 3 2 5样例输出
0 1 0 3 4 3 3 7
思路分析
1.输入处理：首先读取数组大小n，然后读取数组arr。
2.初始化：res数组用于存储结果，初始化为0（表示没有找到符合条件的元素）。
stack用于维护单调递增的索引栈。3.单调栈处理：
遍历数组中的每个元素。
当栈非空且栈顶索引对应的元素值大于等于当前元素值时，弹出栈顶（因为这些元素不可能成为后续元素的答案）。
如果栈非空，栈顶索引对应的元素即为左边最近的小于当前元素的值，将其索引（加1转换为1-based）存入
res[i]。将当前索引压入栈中。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
vector<int>res(n,0);
vector<int>mystack;
for(int i=0;i<n;i++){
while(!mystack.empty()&&arr[mystack.back()]>=arr[i]){
mystack.pop_back();
}
if(!mystack.empty()){
res[i]=mystack.back()+1;
}
mystack.push_back(i);
}
for(int i=0;i<n;i++){
cout<<res[i]<<" ";
}
return 0;
}