1509.Minimum Difference Between Largest and Smallest Value in Three Moves

Tags: Medium Sort Greedy

Links: https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/

---

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

Example 1:

Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.

Example 2:

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1]. 
The difference between the maximum and minimum is 1-0 = 1.

Example 3:

Input: nums = [6,6,0,1,1,4,6]
Output: 2

Example 4:

Input: nums = [1,5,6,14,15]
Output: 1

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

---

题目让求最大值与最小值差的最小值，想到两种思路，一种是二分，一种是贪心。

二分需要寻找单调性来缩小搜索区间，这个单调性却并不是很容易找到。这个题目其实有点类似CodeForces Minimizing Difference，让两端的极值往中间的数靠拢。

首先如果数组内元素的个数小于4，那么可以使数组内的数字都相同，所以直接返回0。

我们将问题一般化，题目虽然指出可以修改三次，如果允许修改k次呢？将数组排序，每次去计算nums[pos + len] - nums[pos]，其中len = n - 1 - k，共计算k + 1次。假设最终最小的差值是左端点位于pos，右端点位于pos + len，那么把0到pos - 1（如果pos > 1的话）的元素都修改为nums[pos]，将pos + len + 1（前提是pos + len + 1 < n）到n - 1的元素全都修改为nums[pos + len]，这样总共只会修改k个元素，修改完后所有的元素值都落在nums[pos]和nums[pos + len]之间了。

可以看出，问题可以泛化到k < n，本题只是k = 3的特殊情况。

只需要计算k + 1次，时间复杂度$O(k)$。

class Solution {
public:
    int minDifference(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int k = 3, n = nums.size(); if (n <= 4) return 0;

        sort(nums.begin(), nums.end());
        int res = INT_MAX;
        int pos = 0, len = n - 1 - k;
        for (int cnt = 0; cnt < k + 1; ++cnt) {
            res = min(res, nums[pos + len] - nums[pos]);
            ++pos;
        }

        return res;
    }
};