Leetcode 1906.查询差绝对值的最小值

题目

一个数组a的差绝对值的最小值定义为:0<=i<j<a.length且a[i]!=a[j]的|a[i]-a[j]|的最小值。如果a中所有元素都相同，那么差绝对值的最小值为-1。
给你一个整数数组nums和查询数组queries，其中queries[i]=[l_i, r_i]。对于每个查询i，计算子数组nums[l_i...r_i]中差绝对值的最小值，子数组nums[l_i...r_i]包含nums数组（下标从0开始）中下标在l_i和r_i之间的所有元素（包含l_i和r_i在内）。
请你返回ans数组，其中ans[i]是第i个查询的答案。
子数组是一个数组中连续的一段元素。

题解

尽管查询数组数量达到2e4，但是nums本身最多也只有1-100，可以暴力枚举记录其中的出现过的数，再根据区间里所出现过的数计算他们的差值。dp[i][j]记录在i位置前j出现了多少次。

class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& q) {
        vector<vector<int>>dp(nums.size()+1,vector<int>(101,0));
        vector<int>ans;
        for(int i=1;i<=nums.size();i++){
            for(int j=1;j<=100;j++)
                dp[i][j]=dp[i-1][j];
            dp[i][nums[i-1]]++;
         }
         int last=-1,minn=INT_MAX;
         for(auto i:q){
            for(int j=1;j<=100;j++)
                if(dp[q[1]+1][j]-dp[q[0]][j]>0){//说明该区间内存在j
                    if(last!=-1) minn=min(minn,j-last);
                    last=j;
                }
            ans.push_back(last>-1?minn:-1);
         }
         return ans;
    }
};