刷题使我快乐，满脸开心.jpg
- 来源：力扣（LeetCode）
- 链接：https://leetcode.cn/problems/moving-stones-until-consecutive-ii
- 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目
在一个长度 无限 的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作 端点石子 。
每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。
值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。
示例 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：
输入：[100,101,104,102,103]
输出：[0,0]
提示：
- 3 <= stones.length <= 10^4
- 1 <= stones[i] <= 10^9
- stones[i] 的值各不相同。
思路
这个题有点意思，具体讲解大家可以参考官方题解，因为我也是没想出来看的题解才会的...
有几个关键点
1、第一就是一个思维上的变换，题目中没有说位置数组中的值是否有序，然而其实值是否有序，对于结果其实并不影响，因为我们需要看的其实是位置之间的空位，至于这个位置在数组中的下标只是在排序之后可以便于执行思路，并不影响位置与位置之间的空余位置，所以可以开始时先做一个排序
2、最大值比较好思考，就是结果中最大位置和结果中最小位置之间的空余位置，为什么说结果中呢，因为第一个移动的一定是左右两个端点石，而根据选择不同，移动之后最终结果就会是1到n-1，或者0到n-2这两个窗口，此时这俩个结果可能是不同的。
也就是题解中提到的
max(stones[n - 2] - stones[0] + 1, stones[n - 1] - stones[1] + 1) - (n - 1);
3、最小值比较难处理，按题解的思路，就是不断的寻找一个窗口，这个窗口需要符合一下两个特征
- 首先自然是不能越界，即
j + 1 < n - 尽可能多的容纳最多的石头，边界为能容纳所有石头，即
stones[j + 1] - stones[i] + 1 <= n
此时一般情况下最小值就是总石头数和窗口中现有石头数的差值，即代码中的
mi = min(mi, n - (j - i + 1))
但是还有一种特殊情况，也就是题解中提到的：
比如 [1,2,3,4,x(x>5)]，此时，
有可能x为6，那自然是移动一次1->5即可，
但是如果x>6，此时就需要先将1->6,再x->5，就需要两步了，即代码中的
mi = min(mi, 2)
当然不需要担心这种情况其实可能只需要移动一次，因为这种情况下，在窗口往后滑动时，会覆盖到总石头数和窗口中现有石头数的差值仅为1的情况，也就可以刷新最小值为1了。
4、位置恰好全部连续时，不能移动，所以最大最小均为0
至此完毕，上代码~
吐槽一句，做习惯了数据结构的题，这种题感觉还是挺难想的，首先得压制住往数据结构靠的思路，，，
代码
func numMovesStonesII(stones []int) []int {
n := len(stones)
sort.Ints(stones)
if stones[n - 1] - stones[0] + 1 == n {
return []int{0, 0}
}
ma := max(stones[n - 2] - stones[0] + 1, stones[n - 1] - stones[1] + 1) - (n - 1)
mi := n
j := 0
for i := 0; i < n; i++ {
for j + 1 < n && stones[j + 1] - stones[i] + 1 <= n {
j++
}
if j - i + 1 == n - 1 && stones[j] - stones[i] + 1 == n - 1 {
mi = min(mi, 2)
} else {
mi = min(mi, n - (j - i + 1))
}
}
return []int{mi, ma}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
/*
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/moving-stones-until-consecutive-ii/solution/yi-dong-shi-zi-zhi-dao-lian-xu-ii-by-lee-8u5g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/