本文主要是介绍力扣每日一题 ---- 1906. 查询差绝对值的最小值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题中，我们的题目求的是差值的最小值，我们考虑一个因素，当前题目中给出的数组是没有排序过的，那么想要求的差值，是不是要两两配对进行判断差值最小值。这里我们就很费时间了，
O(N^2)的时间复杂度，那么我们怎么办呢？排序吗？不太行，排完序的话，后面查询就很麻烦了，不可取，此时我们在注意一下数据，数字只有100，那么这个就是这题的关键点之一了，只有100个数。那么我们再来考虑差值的最小值，差值的最小值是不是只有相邻的两数才行，如果不相邻的话，那么必然不可能是差值最小值。所以这是第二个关键点，贪心，贪的是相邻的数。
那么我们怎么知道区间之内的数有哪些呢，前缀和，但是前缀和我们只知道数有多少个了，那怎么知道该区间有没有这个数，这个我们也是可以通过前缀和知道的，因为我们统计的前缀和是区间内的数字的个数，那么我们就可以知道这个个数了，利用前缀和性质，相减一下就知道个数了。
那么我们利用前缀和求出个数，利用贪心的思想，我们就可以解决这道题目了
class Solution {
public:int ss[111000][110];vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {memset(ss,0,sizeof(ss));ss[1][nums[0]]++;int n = nums.size();for(int i = 2;i <= n;i++){memcpy(ss[i],ss[i - 1],sizeof(ss[i]));ss[i][nums[i - 1]]++;}vector<int> ans;for(auto&q:queries){int prev = -1;int left = q[0];int right = q[1];int res = 0x3f3f3f3f;for(int i = 1;i <= 100;i++){if(abs(ss[right + 1][i] - ss[left][i]) > 0){if(prev != -1){res = min(res,i - prev);}prev = i;}}if(res != 0x3f3f3f3f) ans.push_back(res);else ans.push_back(-1);}return ans;}
};这篇关于力扣每日一题 ---- 1906. 查询差绝对值的最小值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
