LeetCode 1040.移动石子直到连续II

在 X 轴上有一些不同位置的石子。给定一个整数数组 stones 表示石子的位置。

如果一个石子在最小或最大的位置，称其为 端点石子。每个回合，你可以将一颗 端点石子 拿起并移动到一个未占用的位置，使得该石子不再是一颗 端点石子。

值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

以长度为 2 的数组形式返回答案，其中：

answer[0] 是你可以移动的最小次数
answer[1] 是你可以移动的最大次数。

示例 1：

输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。
示例 2：

输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

提示：

3 <= stones.length <= 104
1 <= stones[i] <= 109
stones 的值各不相同。

解：由于我们每次移动只能将两端的石子移动到中间，因此每次移动必定使得石子更加密集。

先定义石子的最大距离为stones[n-1]-stones[0]，对于最大值，我们应该每次移动都使得石子的最大距离减小1，即像跳棋一样，每次都将两端的某个石子移动到距离自己最近的中间位置，如128，首先将位置1的石子移动到2后面，即238，然后再将位置2的石子移动到3后面，即348，同理，后面几步为458、568、678，到678石子就连续了，这种方式每一步使得石子的最大距离都减少了1，移动总步数最大，值为初始情况下两端石子的中间空闲位置的数量，即5。但对于第一步来说，并不总能使石子的最大距离减小1，如137，移动方式一是把7移到13中间，则石子的最大距离缩小了4；方式二则是把1移动到37中间，则石子的最大距离缩小了2；我们应该选择缩小距离较短的方式二。第一步之后，就可以有方法使每次移动距离都只缩小1了。因此最大值的公式为：

$$max(stones[n-2]-stones[0],stones[n-1]-stones[0])-1-(n-3)$$

公式解释：max选出第一步移动时，使距离缩小较短的方式。对于第一步移动右端石子的情况，记stone为s，开区间(s[0], s[n-2])中间有s[n-2] - s[0] - 1个位置，去掉s[0]、s[n-2]、s[n-1]，剩下的n-3个石子占用了这些位置，因此空闲位置数量就是s[n-2] - s[0] - 1 - (n - 3)。对于第一步移动左端石子的情况，同理。

对于最小值，我们可以用滑窗解决，如果有n个石子，我们维护一个n个石子的窗口，看其中有多少个空闲位置，空闲位置数即为移动石子的最小值。但有一种特殊情况，如1678，我们不能把1移动到5或9，因此特殊情况就是一个单独石子+一串连续石子的情况。这种特殊情况的移动次数为2，只需把连续石子中8移动为4，然后再将1移动为5即可。

class Solution {
public:vector<int> numMovesStonesII(vector<int>& stones) {sort(stones.begin(), stones.end());int n = stones.size();int max1 = stones[n - 2] - stones[0] - n + 2;int max2 = stones[n - 1] - stones[1] - n + 2;int maxNum = max(max1, max2);// 如果是特殊情况if (max1 == 0 || max2 == 0) {// 保证最小值小于2return {min(maxNum, 2), maxNum};}int minNum = numeric_limits<int>::max();int left = 0;for (int i = 0; i < n; ++i) {while (stones[i] - stones[left] + 1 > n) {++left;}minNum = min(minNum, n - i + left - 1);}return {minNum, maxNum};}
};

如果有n个石子，则此算法时间复杂度为O(nlogn)，空间复杂度为O(1)。