1906. 查询差绝对值的最小值-动态规划算法

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

一个数组 a 的 差绝对值的最小值 定义为：0 <= i < j < a.length 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值。如果 a 中所有元素都 相同 ，那么差绝对值的最小值为 -1 。

比方说，数组 [5,2,3,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0 ，因为 a[i] 和 a[j] 必须不相等。
1

给你一个整数数组 nums 和查询数组 queries ，其中 queries[i] = [li, ri] 。对于每个查询 i ，计算 子数组 nums[li…ri] 中 差绝对值的最小值 ，子数组 nums[li…ri] 包含 nums 数组（下标从 0 开始）中下标在 li 和 ri 之间的所有元素（包含 li 和 ri 在内）。

请你返回 ans 数组，其中 ans[i] 是第 i 个查询的答案。

子数组 是一个数组中连续的一段元素。

|x| 的值定义为：

如果 x >= 0 ，那么值为 x 。
如果 x < 0 ，那么值为 -x 。
1
2

示例 1：

输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
输出：[2,1,4,1]
解释：查询结果如下：

• queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
• queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
• queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
• queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。

示例 2：

输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
输出：[-1,1,1,3]
解释：查询结果如下：

• queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。
• queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。
• queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。
• queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。

这题感觉挺有难度的，解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* minDifference(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
    int dp[numsSize][101];
    for(int i=0;i<numsSize;i++){
        if(i==0){
            for(int j=0;j<100;j++){
                dp[0][j+1]=0;
            }
            dp[0][nums[i]]++;
        }
        else{
              for(int j=0;j<100;j++){
                //  printf("%d ",j);
               dp[i][j+1]=dp[i-1][j+1];
            }
            dp[i][nums[i]]++;
             
        }

    }
    int *re=(int *)malloc(sizeof(int)*queriesSize);
    * returnSize=queriesSize;
    int r[101];
    int size=0;
    for(int i=0;i<queriesSize;i++){
        int low=queries[i][0]-1,upper=queries[i][1];

         for(int j=0;j<100;j++){
              if(low!=-1){
                  r[j+1]=dp[upper][j+1]-dp[low][j+1];
              }
              else{
                  r[j+1]=dp[upper][j+1];
              }
            }
            int p=1;
            int start;
        while(r[p]==0){p++;
        }
        start=p;
        int min=100;
        for(int j=p+1;j<=100;j++){
            if(r[j]!=0){
                if(abs(j-start)<min){
                    min=abs(j-start);
                }
                start=j;
            }
        }
        if(min==100){ re[size++]=-1;
            }
             else{
                 re[size++]=min;
             }
       
        

    }
    return re;

   

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65