[LeetCode] 1040. Moving Stones Until Consecutive II

[grandyang]

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:

1. 3 <= stones.length <= 10^4
2. 1 <= stones[i] <= 10^9
3. stones[i] have distinct values.

这道题是之前那道 Moving Stones Until Consecutive 的拓展，这里不止三个石头，而是可能有很多石头，每次可以取最大或最小的位置，将其放到中间某个没有石头的位置，注意放的位置不能是新的顺序中的最大或最小的位置，当所有石头位置相连时游戏结束，问最小和最大的移动分别是多少。这里还是要分别来分析两种情况，墙裂推荐 xiongqiangcs 大神的帖子，很贴心的画了图，可以很好的帮助我们理解。先来分析最大的移动次数，由于要尽可能的多移动，所以采取的策略是从最小的位置开始，向右移动到第一个空位，然后再从当前最小的开始，移动到下一个空位，以此类推，直到所有的石头都相连了为止。那么总共的移动次数是多少呢，这里先给数组排个序，最大位置 stones[n-1] 和 最小位置 stones[0] 之间共有 stones[n-1] - stones[0] + 1 个位置，但是中间已经放了 n-2 个石头，所以此时的空位应该是 stones[n-1] - stones[0] + 1 - (n - 2) 即 stones[n-1] - stones[0] - n + 1 个。那么最大移动步数就是最大空位数吗，其实不一定，因为题目中有个限定条件，石子移动到的位置不能是新顺序中的最大或最小的位置，所以当最小位置和第二小位置中间有空位的时候，最小位置的石头是不能走的，比如 1 3 4 6，石子1不能走到2上，但是我们可以将最大的石子6放到2上，这样就可以交替前行了，那么实际上相当于少了一个石子，且多增加了一步，于是步数为 stones[n-2] - stones[0] - n + 2。同理，我们也可以将最小的石子1线填充到位置5，然后从后往前交替进行，这样的步数是 stones[n-1] - stones[1] - n + 2，则最大的步数就是这二者中的较大值了。接下来看最小步数怎么求，这里实际上要用到一个滑动窗口 Sliding Window 的概念，希望能找到一个长度正好为n的窗口，然后计算出当前窗口中已经有的数字个数，那么总个数减去已经有的个数就是最小步数。这个窗口的左右边界分别就是任意两个数字，若这两个数字的距离超过了n，则跳过。不大于n的时候，则可以通过下标算出该窗口中已经有的数字的个数，若正好有了 n-1 个数字，且窗口的大小也是 n-1，则就是题中例子2的那种情况，这时窗口里的数字已经连续了，窗口外的剩余的唯一的数字没法直接加到两边，只能移动两次来实现全部连续，这时候就要跟2比取较小值。而其他情况则直接跟窗口中的空位个数比较即可，参见代码如下：

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size(), low = n, i = 0;
        for (int j = 0; j < n; ++j) {
            while (stones[j] - stones[i] + 1 > n) ++i;
            int already_store = j - i + 1;
            if (already_store == n - 1 && stones[j] - stones[i] + 1 == n - 1) {
                low = min(low, 2);
            } else {
                low = min(low, n - already_store);
            }
        }
        return {low, max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2)};
    }
};

Github 同步地址:

#1040

类似题目：

Moving Stones Until Consecutive

参考资料：

https://leetcode.com/problems/moving-stones-until-consecutive-ii/

https://leetcode.com/problems/moving-stones-until-consecutive-ii/discuss/289357/c%2B%2B-with-picture

https://leetcode.com/problems/moving-stones-until-consecutive-ii/discuss/286707/JavaC%2B%2BPython-Sliding-Window

LeetCode All in One 题目讲解汇总(持续更新中...)