1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| const int N = 100001, M = 101;
int s[N][M];
class Solution {
public:
vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
const int n = nums.size(), m = queries.size();
for (int i = 1; i <= nums.size(); ++i)
for (int j = 1; j <= 100; ++j) {
s[i][j] = s[i - 1][j];
if (nums[i - 1] == j) ++s[i][j];
}
vector<int> ans(m);
for (int i = 0; i < m; ++i) {
int l = queries[i][0] + 1, r = queries[i][1] + 1, pre = 0, res = M;
for (int j = 1; j <= 100; ++j)
if (s[r][j] > s[l - 1][j]) {
if (pre) res = min(res, j - pre);
pre = j;
}
ans[i] = res == M ? -1 : res;
}
return ans;
}
};
|