Related: LeetCode 1033 - moving stones until consecutive
https://leetcode.com/problems/moving-stones-until-consecutive-ii/
On an infinite number line, the position of the i-th stone is given by
stones[i]. Call a stone an endpoint stone if it has the smallest or largest position.
Each turn, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.
In particular, if the stones are at say,
stones = [1,2,5], you cannot move the endpoint stone at position 5, since moving it to any position (such as 0, or 3) will still keep that stone as an endpoint stone.
The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.
When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array:
answer = [minimum_moves, maximum_moves]
Example 1:
Input: [7,4,9] Output: [1,2] Explanation: We can move 4 -> 8 for one move to finish the game. Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game.
Example 2:
Input: [6,5,4,3,10] Output: [2,3] We can move 3 -> 8 then 10 -> 7 to finish the game. Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game. Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move.
Example 3:
Input: [100,101,104,102,103] Output: [0,0]
Note:
3 <= stones.length <= 10^41 <= stones[i] <= 10^9stones[i]have distinct values.
Lower Bound
As I mentioned in my video last week,
in case of
we need to find a consecutive
in case of
n stones,we need to find a consecutive
n positions and move the stones in.
This idea led the solution with sliding windows.
Slide a window of size
We want moves other stones into this window.
For each missing stone, we need at least one move.
N, and find how many stones are already in this window.We want moves other stones into this window.
For each missing stone, we need at least one move.
Generally, the number of missing stones and the moves we need are the same.
Only one corner case in this problem, we need to move the endpoint to no endpoint.
Only one corner case in this problem, we need to move the endpoint to no endpoint.
For case
1 move needed from
1,2,4,5,10,1 move needed from
10 to 3.
For case
2 move needed from
1,2,3,4,10,2 move needed from
1 to 6, then from 10 to 5.Upper Bound
We try to move all stones to leftmost or rightmost.
For example of to rightmost.
We move the
Then each time, we pick the stone of left endpoint, move it to the next empty position.
During this process, the position of leftmost stones increment 1 by 1 each time.
Until the leftmost is at
For example of to rightmost.
We move the
A[0] to A[1] + 1.Then each time, we pick the stone of left endpoint, move it to the next empty position.
During this process, the position of leftmost stones increment 1 by 1 each time.
Until the leftmost is at
A[n - 1] - n + 1.Complexity
Time of quick sorting
Time of sliding window
Space
O(NlogN)Time of sliding window
O(N)Space
O(1) public int[] numMovesStonesII(int[] A) {
Arrays.sort(A);
int i = 0, n = A.length, low = n;
int high = Math.max(A[n - 1] - n + 2 - A[1], A[n - 2] - A[0] - n + 2);
for (int j = 0; j < n; ++j) {
while (A[j] - A[i] >= n) ++i;
if (j - i + 1 == n - 1 && A[j] - A[i] == n - 2)
low = Math.min(low, 2);
else
low = Math.min(low, n - (j - i + 1));
}
return new int[] {low, high};
}
https://leetcode.com/problems/moving-stones-until-consecutive-ii/discuss/287207/No-Code-English-explanation
I tried my best to translate it into English.
First, sort the position of stones in ascending order.
- How to find the maximum:
Each time you can move the leftmost or rightmost, so the maximum value must come from either move the leftmost first or the rightmost first;
If you move the rightmost for the first time, the first step must be to move it to the left of stones[n-2], where n is the length of stones, and the leftmost position is stones[0],
Therefore, the moving distance is stones[n-2]-stones[0]-1-(n-3), which is the position inside the current interval, minus the number of stones already in the interior (there are 3 not in the interval, they are left and right ends of the interval and stones[n-1]), and the remaining empty position is the position where the stone can be moved.
Therefore, the moving distance is stones[n-2]-stones[0]-1-(n-3), which is the position inside the current interval, minus the number of stones already in the interior (there are 3 not in the interval, they are left and right ends of the interval and stones[n-1]), and the remaining empty position is the position where the stone can be moved.
For example: [1,3,5,7,12,65], there are 7 empty slots between 1 and 12, that is, move the right end first, and can move up to 7 times.
Similarly, if you move the leftmost end for the first time, the first step must be to move it to the right of the stones[1], the rightmost end of which is stones[n-1],
Therefore the moving distance is stones[n-1]-stones[1]-1-(n-3);
Therefore the moving distance is stones[n-1]-stones[1]-1-(n-3);
For example: [1,3,5,7,12,65], there are 58 empty slots left between 3 and 65, that is, the left end is moved first, and the maximum movement is 58 times.
The maximum value of the above two values is the two number of steps that can be moved currently.
- How to find the minimum:
idea comes from sliding window, continuously constructing an interval, this interval [i, j] will satisfy: the length of the interval should not be greater than the number of stones, that is, this interval can be filled with stones outside the interval (some stones can still be outside the interval) .
Then check if this interval is consecutive and there is only one leftmost or rightmost stone not in this consecutive interval, then this is the corner case, returning 2.
For example, [1, 2, 3, 4, 10], the interval [1, 2, 3, 4] is consecutive, but there is only one external stone, you need to put 1 to the position 6, then put 10 to position 5.
If it isn't the corner case mentioned above, then it is not necessary to check whether the stones positions in the interval is consecutive or not, that is, put the numbers other than the [i, j] interval into the [i, j] interval, and let them be consecutive, only need n - (j-i+1) step.
E.g:
Intervalis not consecutive inside:
[1,4,7,9,20,30], the current i is 0, j is 1, we need only 4 steps to make [7,9,20,30] and [1,4] consecutive.
- Put 30 in the 6 position, [1,4,6,7,9,20];
- Put 20 in the 5 position, [1,4,5,6,7,9];
- Put 9 in the position of 3, [1, 3, 4, 5, 6, 7];
4 .Put 7 in the 2 position, [1, 2, 3, 4, 5, 6] and end.
Interval is consecutive inside:
[1,2,3,56,89], i is 0, j is 2, only 2 steps
- Put 89 in the position of 5, [1, 2, 3, 5, 56];
- Put 56 into the 4 position, [1, 2, 3, 4, 5], and end
在一个长度无限的数轴上，第
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，游戏结束。
输出：[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 这样的移动来结束游戏，因为这是不合要求的移动。
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。
示例 3：
输入：[100,101,104,102,103]
输出：[0,0]
输出：[0,0]
思路：最终的状态是连续的一段区间，可以等价为 用一段连续区间（长度为len(stones)）去覆盖原始数组，分别求最多，最少覆盖的element个数， 很容易想到sliding window
1. 但是要考虑corner case，比如对于下界：3,4,5,6,10 长度为5的区间最多覆盖4个element（3,4,5,6，比如可以用3-7,4-8区间），但是这些区间确是非法的，因为边界点（7,8）无法通过10移动得到（10移动到7,8还是end point），
所以在sliding window要侦测这种情况，并特殊处理
2. 如果上界用上述方法求解，corner case更多，但是有一种方法比较简单，即：上界是以下2者之一：全移到左边，全移到右边
首先对
stones升序排序。
求最大值：
每次可以移动最左端或者最右端，因此最大值一定是要么第一次移动的是最左端，要么第一次移动的是最右端；
如果第一次移动最右端，那么第一步一定是移到最右边开始第二个的前面，即
因此移动距离就是
stones[n-2]，n为stones的长度，并且最左的位置是stones[0]，因此移动距离就是
stones[n-2]-stones[0]-1-(n-3)，也就是当前区间内部的位置，减去内部已经有石头的数量(有3个不在区间内部，分别是区间左右端2个和最后1个stones[n-1])，剩下的空位置就是能移动石头的位置。
例如：
[1,3,5,7,12,65]，1到12之间还剩下7个空位置，也就是先移动右端，能最多移动7次。
同样的，如果第一次移动最左端，那么第一步一定是移动到最左边开始第二个的后面，即
因此移动距离就是
stones[1]，它的最右端即是stones[n-1]，因此移动距离就是
stones[n-1]-stones[1]-1-(n-3)；
例如：
[1,3,5,7,12,65]，3到65之间还剩下58个空位置，也就是先移动左端，能最多移动58次。
上面两个值取最大值就是当前能移动的最大步数。
求最小值：
window slide，不断构造一个区间，这个区间[i,j]满足，区间的长度不会大于石头的数量，即这个区间是可以被区间外部的石头塞满的(可以塞不下，但不能有空隙)。
接着检查如果这个区间是连续的并且外部非连续的只有1个，那么这是一种特殊情况，返回
2。
例如
[1,2,3,4,10]，区间[1,2,3,4]是连续的，但外部非连续的只有1个，需要将1放到6的位置，再将10放到5的位置。
如果不是以上的特殊情况，那么不需要检查区间内部是否连续了，也就是将除了
[i,j]区间以外的数字放入[i,j]区间，放不下的要让它们连续，只需要n-(j-i+1)步。
例如：
区间内部不连续：
[1,4,7,9,20,30]，当前i为0，j为1，那么将[7,9,20,30]与[1,4]连续只需要4步- 将
30放入6的位置，[1,4,6,7,9,20]； - 将
20放入5的位置，[1,4,5,6,7,9]； - 将
9放入3的位置，[1,3,4,5,6,7]； - 将
7放入2的位置，[1,2,3,4,5,6]，结束。
区间内部连续：
[1,2,3,56,89]，i为0，j为2，只需要2步- 将
89放入5的位置，[1,2,3,5,56]； - 将
56放入4的位置，[1,2,3,4,5]，结束
X 枚举+二分 或 滑动窗口+贪心
https://leetcode.com/problems/moving-stones-until-consecutive-ii/discuss/291744/ChineseC%2B%2B-1040.-%2B-%2B
给一些互不相同的数字，每次可以将最大的数字或者最小的数字进行修改。修改后这个值不能是最大值和最小值。
最终不能移动时，结束。求移动的最大步数和最小步数。
最终不能移动时，结束。求移动的最大步数和最小步数。
思路：
对于最大步数，肯定是一步步的移动。
由于规则的限制，第一次移动可能不是一步，而是很多步，之后可以一步步移动。
所以第一次移动时，选择步数最小的（最左端和最右端两个数字选一个），之后就是有多少个空位置，就可以移到多少次。
对于最大步数，肯定是一步步的移动。
由于规则的限制，第一次移动可能不是一步，而是很多步，之后可以一步步移动。
所以第一次移动时，选择步数最小的（最左端和最右端两个数字选一个），之后就是有多少个空位置，就可以移到多少次。
而对于最小步数，则是尽可能所有数字只移动一次。
做题的时候，我的思路是暴利枚举。
假设数字最终区间确定，那么移动的最小步数也是确定的。
枚举所有可能的区间，然后分情况计算最小步数。
做题的时候，我的思路是暴利枚举。
假设数字最终区间确定，那么移动的最小步数也是确定的。
枚举所有可能的区间，然后分情况计算最小步数。
分情况讨论：
先来看一个特殊情况：连续数字是n-1个且最小值或最大值不是连续数字，此时需要两步，而不是一步。
接下来看看讨论吧。
假设最终目标区间是
如果
如果
如果
其他情况则说明两边个数都是至少两个，肯定存在答案。这个又根据
假设最终目标区间是
[a,b]，我们分别计算小于等于a的个数与大于等于b的个数。如果
a和b两个位置都有数字，那这个区间之外的数字可以直接移动到区间内，最小步数就是这个区间之外的数字个数。如果
a和b有都没值，且只有一个数字小于a一个数字大于b， 则肯定没有答案（最值无法移动到最值）。如果
a和b至少有一个没值，例如a没值，且只有一个数字小于a， 则肯定没有答案（最值无法移动到最值）。其他情况则说明两边个数都是至少两个，肯定存在答案。这个又根据
a与b边界是否有值分两种情况，就不多说了。
当然这道题最优答案是贪心计算。
贪心假设：找到区间内最长的数字个数，则其他数字都应该移到到这个最大的连续数字附近。
需要移动的步数就是不在这个区间内的个数。
贪心假设：找到区间内最长的数字个数，则其他数字都应该移到到这个最大的连续数字附近。
需要移动的步数就是不在这个区间内的个数。
贪心证明：根据上面的二分也可以看出，如果有答案，答案则为最终区间之外的数字个数。
除了最开始题意说的特殊情况，这种特殊判断一下就行了。
除了最开始题意说的特殊情况，这种特殊判断一下就行了。
