910. Smallest Range II
1 | class Solution { |
这道题真是想了好久.
每个数字要么是加k, 要么是减去k, 这等效于每个数字要么不变, 要么加2k, 因为假设我们规定好每个数字是加k还是减k, 之后我们让所有的数字统一都加k, 此时最大值和最小值之间的差是不变的, 但是之前减去k的数字变回了原样, 加k的数字变成了加2k. 知道这个后, 我们的思路就是让每个数字都加2k, 在这种情况下求最大值最小值之间的差, 然后取全局最优即可.
首先我们要sort一下, 比如我们让i这个位置加上2k. 它加上后, 我们想象一个区间, 一端是nums[0], 另一端是nums[i] + 2k. 此时nums[1], nums[2],… nums[i] + 2k都在这个区间中, 我们的目的是让区间缩小, 于是我们可以让i之前的所有数字都加上2k, 这样区间的右端不会变(因为array是sort的, i之前的数字加上2k也不会比nums[i] + 2k大), 左端就往右缩了一些. 那对于i右边的数字, 它们组成的区间是[nums[i + 1], nums[nums.length - 1]]. 那这些数字需要加2k吗? 可以这么想. 我们称之前得到的区间为m. 如果i右侧的数字在m内部, 那么不需要加2k, 因为加不加都不会改变m的长度, 甚至如果加了还会让m的区间右端变大. 如果i右侧数字在m的右侧, 那就更不需要加了, 这会让区间扩得更大. 最后是如果i右侧的数字有在m左侧的. 我们需要分类讨论, 如果加上2k后是小于等于m区间的右端, 那我们是可以加的; 如果是大于, 我们需要比较加之前和加之后哪个区间更短来判断加还是不加.
上面讨论的唯一可能加的情况就是i右侧小于m区间的数字. 这些数字一定是从i + 1开始到达某个位置时进入m区间或者到达array末尾, 因为array是sort好的. 那么假设我们知道从i + 1开始哪些数字需要加2k, 此时得到当下最短的array.假设最后一个加2k的数字的index是j. 那么等我们到达j的时候, 也会想一个问题就是j右侧的数字是在此时区间的什么位置. 我们在之前位置的时候就知道j右侧的数字在m区间中或者右侧, 那到达j位置的时候, j右侧的数字一定在此时的区间内或者右侧, 因为此时j的区间变大了而且左端和之前区间的左端都相同. 因此我们可以这样, 在之前区间的时候, i右侧数字都不加2k, 此时得到的最大最小可能不是正确的答案, 但是当我们到j的时候, i时候的最大最小答案这种情况我们就可以cover上. 这就是关键.
时间复杂度: O(nlogn)
空间复杂度: O(1)