2020/3/15
题目描述
在一个长度无限的数轴上，第 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] 的值各不相同。
相关标签
数组
sliding window
解题思路
-
算法：
由题意可知，每进行一轮操作，石子的左右端点的距离会缩短，一轮一轮收敛。最后会石子都紧邻游戏结束。
举个例子：
初始时有 8 颗石子，在数轴上的有石子的刻度为：
4，6，8，9，15，16，19，20
最大值求解方法：
石子可以放置的空间，等于左右两端石子之间的未占用位置。在例子中，一共有 20-4+1-8 个位置。
石子覆盖的线段长度是 20-4 个，加上一个端点的位置即 20-4+1，再减去已经占用的 8 个位置。
用公式表示为：
s1 = stones[n-1] - stones[0] + 1 - ns1 = stones[n−1] − stones[0] + 1 − n
但是第一次移动的左端点或右端点的石子后，这个移动的石子和它相邻的那颗石子之间的空间，后面就不能被放置了，因为与他相邻的那个点变为端点，他们之间的位置不可以被放置了。
例如第一步移动了 4，那么 5 这个位置就不可能放置石子了。所以要计算不能被访问的空间
s2 = min(stones[n1] - stones[n2] -1, stones[1] - stones[0] - 1)
最大值为 s1-s2。因为在后面的步骤里，我们都可以做出策略，让每一轮左右端点的差值只减 1。
最小值求解方法：
如果最后游戏结束，那么一定有 nn 个连续坐标摆满了石子。如果我们要移动最少，必定要找一个石子序列，使得在 nn 大小连续的坐标内，初始时有最多的石子。
设想有个尺子，上面有 nn 个刻度点，我们用这个尺子在石子从最左边到最右边移动，每动一次都查看下在尺子范围内有 mm 个石子，那么要使这个区间填满，就需要移动 n-mn−m 次。
只要在尺子外部有石子，就有策略填满尺子内的。
这些次数中最小的就为虽少次数。
但是有一种特例：
1，2，3，4，7
这种 1-4 是最好的序列，但是 7 不能移动到端点，只能 1 先移动到 6，然后 7 移动到 5 解决，这种情况要用 2 步。就是尺子内的石子都是连续的，中间没空洞，只在边上有空，要用 2 次。
-
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(1)
源代码
impl Solution {
pub fn num_moves_stones_ii(mut stones: Vec<i32>) -> Vec<i32> {
stones.sort();
let len = stones.len();
let mut min = std::i32::MAX;
// 计算最大移动次数
let space_init = stones[len-1] - stones[0] - len as i32 + 1;
let space_after_first_move = space_init - std::cmp::min(stones[len-1] - stones[len-2] - 1, stones[1] - stones[0] - 1);
// 计算最小移动次数
for i in 0..len {
let (mut t, mut j) = (0, i);
while j < len {
if stones[j] - stones[i] < len as i32 {
t += 1
}
else {
break;
}
j += 1;
}
j -= 1;
min = std::cmp::min(min, len as i32 - t);
if t == len as i32 - 1 && min != 0 && stones[j] - stones[i] + 1 != len as i32 { min += 1 };
}
vec![min, space_after_first_move]
}
}
执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 2.3 MB, 在所有 Rust 提交中击败了100.00%的用户
总结
求最小值的方法具有一定的普遍性。
