移动石子直到连续 II【LC1040】
在一个长度 无限 的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作 端点石子 。
每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。
值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。
这几天一直在干活 然后昨天下午做题一直被打断 最后我都以为自己已经发好题解了 结果并没有发…
- 思路
- 首先，明确每次移动时只能移动端点，并且端点移动后不能还是端点，即移动后石子的左侧和右侧必须有其他石子。每次移动后两边端点的距离较小
- 什么时候无法移动？
所有石子之间没有空位，都位于连续的n个位置
- 如何获得最大移动次数？
每次移动，都让移动的距离尽可能小【贪心】，那么移动次数就能达到最大。
那么第一次移动存在两种移动方式
- 移动
stones[0]至stones[1]+1 - 移动
stones[n-1]至stones[n-2]-1
而我们之后的每次移动都可以使移动距离为1，从而获得最大的移动次数，移动的次数取决于第一次移动后新端点之间的空位，即
s[n−1]−s[1]−1−(n−3)=s[n−1]−s[1]−n+2
s[n−2]−s[0]−1−(n−3)=s[n−2]−s[0]−n+2
因此，最大移动次数为
max(s[n−1]−s[1]−n+2,s[n−2]−s[0]−n+2)
如何获得最小移动次数？
由于所有端点可以移动至可以中间任意的空位，那么我们应该尽可能将石子移动至最合适的问题。
那么我们可以枚举长度为n的滑动窗口，计算其中没有石子的位置的个数，取最小值返回。
但此时存在特殊情况，即移动后石子仍为端点的情况
于是，我们需要判断，s[0]至s[n−2]和s[1]至s[n−1]之间是否有空位，如果没有空位，那么答案为2；还需比较与最大移动次数的关系，如果最小移动次数应小于最大移动次数
- 滑动窗口
- 实现
class Solution { public int[] numMovesStonesII(int[] s) { Arrays.sort(s); int n = s.length; int e1 = s[n - 2] - s[0] - n + 2; int e2 = s[n - 1] - s[1] - n + 2; // 计算空位 int maxMove = Math.max(e1, e2); if (e1 == 0 || e2 == 0) // 特殊情况：没有空位 return new int[]{Math.min(2, maxMove), maxMove}; int maxCnt = 0, left = 0; for (int right = 0; right < n; ++right) { // 滑动窗口：枚举右端点所在石子 while (s[right] - s[left] + 1 > n) // 窗口长度大于 n ++left; // 缩小窗口长度 maxCnt = Math.max(maxCnt, right - left + 1); // 维护窗口内的最大石子数 } return new int[]{n - maxCnt, maxMove}; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/moving-stones-until-consecutive-ii/solutions/2212638/tu-jie-xia-tiao-qi-pythonjavacgo-by-endl-r1eb/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
