数组中含重复元素的情况下,寻找每个元素左边和右边比当前元素小的位置。
单调栈实现
思路:栈内元素是一个链表,用链表保存相同元素出现的所有位置,然后出栈的时候依次遍历每个位置。
实现:使用vector实现不定长的数组,取最后一个元素是back()操作
#include<stack>
#include<vector>
using namespace std;
int main(){
int n;
scanf("%d", &n);
int nums[n];
for(int i=0;i<n;i++){
scanf("%d", &nums[i]);
}
int result[n][2];
int L,R;
stack<vector<int>>stk;
for(int i=0;i<n;i++){
while(!stk.empty() && nums[i]<nums[stk.top().back()]){
vector<int>cur=stk.top();
stk.pop();
if(stk.empty()){
L=-1;
}
else{
L=stk.top().back();
}
R=i;
//给相同的每个位置都赋值
for(int j=0;j<cur.size();j++){
result[cur[j]][0]=L;
result[cur[j]][1]=R;
}
}
if(!stk.empty() && nums[i]==nums[stk.top().back()]){
stk.top().push_back(i);
}
else{
vector<int>position;
position.push_back(i);
stk.push(position);
}
}
while(!stk.empty()){
vector<int>cur=stk.top();
stk.pop();
if(stk.empty()){
L=-1;
}
else{
L=stk.top().back();
}
R=-1;
//给相同的每个位置都赋值
for(int j=0;j<cur.size();j++){
result[cur[j]][0]=L;
result[cur[j]][1]=R;
}
}
for(int i=0;i<n;i++){
printf("%d %d\n",result[i][0], result[i][1]);
}
return 0;
}