一个数组 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] 必须不相等。
给你一个整数数组 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:输入: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 。
提示:2 <= nums.length <= 105
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 104
0 <= li < ri < nums.length
1、前缀和;时间复杂度O(n),空间复杂度O(n)
func minDifference(nums []int, queries [][]int) []int {
n := len(nums)
arr := make([][101]int, n+1)
for i := 1; i <= n; i++ {
arr[i] = arr[i-1]
arr[i][nums[i-1]]++
}
res := make([]int, len(queries))
for i := 0; i < len(queries); i++ {
res[i] = -1
left, right := queries[i][0], queries[i][1]
prev, minValue := 0, math.MaxInt32
for j := 1; j <= 100; j++ { // 枚举每个数
if arr[right+1][j] != arr[left][j] { // 当j出现
if prev != 0 {
if j-prev < minValue { // 保存较小的差值
minValue = j - prev
}
}
prev = j // 更新上一个出现的数
}
}
if minValue != math.MaxInt32 {
res[i] = minValue
}
}
return res
}
2、树状数组;时间复杂度O(nlog(n)),空间复杂度O(n)
func minDifference(nums []int, queries [][]int) []int {
n := len(nums)
length = n
c = make([][]int, 101) // 存储每个数对应顺序区间出现的次数
for i := 0; i < 101; i++ {
c[i] = make([]int, n+1)
}
for i := 1; i <= n; i++ {
upData(nums[i-1], i, 1)
}
res := make([]int, len(queries))
for i := 0; i < len(queries); i++ {
res[i] = -1
left, right := queries[i][0], queries[i][1]
prev, minValue := 0, math.MaxInt32
for j := 1; j <= 100; j++ { // 枚举每个数
count := getSum(j, right+1) - getSum(j, left)
if count > 0 { // 当j出现
if prev != 0 {
if j-prev < minValue { // 保存较小的差值
minValue = j - prev
}
}
prev = j // 更新上一个出现的数
}
}
if minValue != math.MaxInt32 {
res[i] = minValue
}
}
return res
}
var length int
var c [][]int // 树状数组
func lowBit(x int) int {
return x & (-x)
}
// 单点修改
func upData(index, i, k int) { // 在i位置加上k
for i <= length {
c[index][i] = c[index][i] + k
i = i + lowBit(i) // i = i + 2^k
}
}
// 区间查询
func getSum(index, i int) int {
res := 0
for i > 0 {
res = res + c[index][i]
i = i - lowBit(i)
}
return res
}
Medium题目,使用前缀和或者树状数组
页面更新:2024-05-13
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号