LeetCode 910. 最小差值 II

Categories:

题目描述
思路分析
1. 解法一：排序 + 枚举分割点（推荐）
相似题目

题目描述

✅ 910. 最小差值 II

思路分析

解法一：排序 + 枚举分割点（推荐）

核心思路：

排序后，假设前半部分加 K，后半部分减 K。

枚举分割点 i，最大值为 max(nums[i] + K, nums[n-1] - K)。

最小值为 min(nums[0] + K, nums[i+1] - K)。

取所有分割点的最小差值。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(1) 额外空间（排序除外）。

import java.util.Arrays;

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = nums[n - 1] - nums[0];

        for (int i = 0; i < n - 1; i++) {
            int high = Math.max(nums[i] + k, nums[n - 1] - k);
            int low = Math.min(nums[0] + k, nums[i + 1] - k);
            ans = Math.min(ans, high - low);
        }

        return ans;
    }
}

import "sort"

func smallestRangeII(nums []int, k int) int {
	sort.Ints(nums)
	n := len(nums)
	ans := nums[n-1] - nums[0]

	for i := 0; i < n-1; i++ {
		high := nums[n-1] - k
		if nums[i]+k > high {
			high = nums[i] + k
		}

		low := nums[0] + k
		if nums[i+1]-k < low {
			low = nums[i+1] - k
		}

		if high-low < ans {
			ans = high - low
		}
	}

	return ans
}

相似题目

题目	难度	考察点
462. 最小操作次数使数组元素相等 II	中等	排序
164. 最大间距	困难	排序
628. 三个数的最大乘积	简单	排序
209. 长度最小的子数组	中等	贪心
495. 提莫攻击	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/73076691