单调栈二分思路
C++ 代码
# include<iostream>
# include<cstring>
# include<algorithm>
using namespace std;
const int N = 100010;
int w[N];
int stk[N],top;
int ans[N];
int n;
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> w[i];
}
for(int i=n-1;i>=0;--i){
if(!top || w[i] <= w[stk[top]]){
ans[i] = -1;
}else{
// 单调栈二分 找到第一个比w[i]小的元素对应下标
int l = 1,r = top;
while(l < r){
int mid = (l + r) >> 1;
if(w[stk[mid]] < w[i]) r = mid;
else l = mid + 1;
}
ans[i] = stk[l] - i - 1;
}
// 更新单调栈 等于时不需要更新 维护严格单调递减
if(!top || w[i] < w[stk[top]]){
stk[++top] = i;
}
}
for(int i=0;i<n;++i) cout << ans[i] << " ";
cout << endl;
return 0;
}
哈希表+二分
# include<iostream>
# include<cstring>
# include<algorithm>
# include<map>
using namespace std;
const int N = 100010;
int w[N];
int stk[N],top;
map<int,int> mp;
int ans[N];
int n;
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> w[i];
}
// 维护一个单调递增的map (负数,索引)
for(int i=n-1;i>=0;--i){
// 二分查找 第一个比当前值大的元素
auto it = mp.upper_bound(-w[i]);
if(it == mp.end()) ans[i] = -1;
else ans[i] = it->second - i - 1;
if(mp.empty() || -(mp.rbegin()->first) > w[i]){
mp.insert({-w[i],i});
}
}
for(int i=0;i<n;++i) cout << ans[i] << " ";
cout << endl;
return 0;
}