当前位置：首页 > article >正文

计算左边（比自己小的元素）的最长距离

article 2024/11/13 16:22:27

前言：一般做的题目都是使用单调栈来求出距离这个点最近的那个比这个数大或小的元素，但是如果是需要找到最远的那个元素呢？我们可以用到类似逆序对的思路，我们先进行排序从小到大，接着我们先处理左边，每次维护一个最小的下标

题目地址

在这里插入图片描述

struct node
{
    node(){
        a = 0, id = 0;
    }
    int a,id;
    bool operator<(node b){
        if(a < b.a) return 1;
        if(a==b.a) return id < b.id;
        return 0;
    }
}sto[50005];


class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<nums.size();i++){
            sto[i].id = i; sto[i].a = nums[i];
        }
        sort(sto,sto+n);
        int ans = 0;
        int xiao = sto[0].id;
        for(int i=1;i<n;i++){
            int u = sto[i].id;
            if(u>xiao){
                ans = max(ans,u-xiao);
            }else{
                xiao = u;
            }
        }return ans;
    }
};