单调栈

链接

题目给出n个数,要求找到某一数字右边第一个大于它的数字的编号

由于数据很大,直接暴力枚举恐怕不太行

那么,我们需要知道怎么才能减少索引次数,以达缩短时间的目的

假设给出一段数据

6 4 2 3 1 7

从后往前是必要的,因为我们可以提前排除一些不必要的索引,比如最后的 3 1 7

1显然是不必索引的,因为前面的数如果大于3,那么就一定大于1,所以

我们只需要保存一个单调递减(从右往左)的数据

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<long>ans;
    vector<int>nums(n,0);
    stack<int>st;
    for(int i=0;i<n;i++){
        long num;cin>>num;
        ans.push_back(num);
    }
   for(int i=n-1;i>=0;i--){
       while(!st.empty()&&ans[st.top()]<=ans[i]){
           st.pop();
       }//这里进行处理没必要索引的数字
       if(!st.empty()){
           nums[i]=st.top()+1;
       }
       else{
           nums[i]=0;
       }
       st.push(i);
   }
    for(int number:nums){
        cout<<number<<" ";
    }
    
}

时间复杂度:O(n)

空间复杂度:O(n)