1033. 移动石子直到连续
难度中等50
三枚石子放置在数轴上，位置分别为 a，b，c。
每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]
示例 1：
输入：a = 1, b = 2, c = 5
输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。
示例 2：
输入：a = 4, b = 3, c = 2
输出：[0, 0]
解释：我们无法进行任何移动。
提示：
1 <= a <= 1001 <= b <= 1001 <= c <= 100a != b, b != c, c != a
分类讨论
https://leetcode.cn/problems/moving-stones-until-consecutive/solution/tan-xin-ji-suan-pythoner-xing-100-1033-y-gj78/
class Solution:
"""
排序后，分类讨论
1. 计算最大步数，最大步数：每次移动1个单位
贪心：将a逐步移至b-1，c逐步移至b+1
c - a - 2
2. 计算最小步数，分类讨论
情形 判断条件 最小步数
1 abc连续 a+2==c 0
2 ab连续 bc不连续 b==a+1 1
3 ab不连续 bc连续 b==c-1 1
4 ab差2 bc不连续[1,3,9] b==a+2 1
5 ab不连续 bc差2[1,7,9] b==c-2 1
6 其他 [1,5,8] 2
"""
def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
a, b, c = sorted([a, b, c])
maxdis = c - a - 2
mindis = inf
if a + 2 == c:
mindis = 0
elif b == a+1 or b == c-1 or b == a+2 or b == c-2:
mindis = 1
else: mindis = 2
return mindis, maxdis
合并成一句
class Solution:
def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
a, b, c = sorted([a, b, c])
return 0 if a + 2 == c \
else 1 if b in (a + 1, c - 1, a + 2, c - 2) \
else 2, c - a - 2
拓展：如果有一万颗石子，该怎么做？
1040. 移动石子直到连续 II
难度中等214
在一个长度 无限 的数轴上，第 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^41 <= stones[i] <= 10^9stones[i]的值各不相同。
分类讨论（下跳棋）
题解：https://leetcode.cn/problems/moving-stones-until-consecutive-ii/solution/tu-jie-xia-tiao-qi-pythonjavacgo-by-endl-r1eb/
class Solution {
/**
最大移动次数：
每次移动，让端点距离缩小1（下跳棋）
最小移动次数：
端点可以直接移动到中间任意空位，直接一步到位
*/
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};
}
}
python
class Solution:
def numMovesStonesII(self, stones: List[int]) -> List[int]:
stones.sort()
n = len(stones)
e1 = stones[-2] - stones[0] - n + 2
e2 = stones[-1] - stones[1] - n + 2
# 最大移动次数等于两种情况空位个数的最大值
max_move = max(e1, e2)
if e1 == 0 or e2 == 0: # 特殊情况。没有空位
return [min(2, max_move), max_move]
max_cnt = left = 0
for right, sr in enumerate(stones): # 滑动窗口：枚举右端点所在石子
while sr - stones[left] + 1 > n: # 窗口长度大于 n
left += 1 # 缩小窗口长度
max_cnt = max(max_cnt, right - left + 1) # 维护窗口内的最大石子数
return [n - max_cnt, max_move]
0x3f
问: 你是如何想到本题的做法的? 是否有一些通用的思考方式?
答:个人觉得这题有点构造的味道 (想算出答案，要大致知道怎么移动石子) 。对于构造题，通常是先从最基本的情况开始思考，比如本题就是从 n = 3 开始思考。在纸上多画一画，比较不同的移动方案，猜想出一个大致的结论。接着思考 n = 4,5,…的情况，验证/修正你的结论。这就是 [从特殊到一般]。如果你想做更多的构造题，可以去 Codeforces 搜索 tag: constructive algorithms。
