晨哥Leetcode 1040. Moving Stones Until Consecutive II

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

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.

解析：

这道题要找规律，比较麻烦

要把最多的move数和最少的move数分开来求。

先排序。

1. 最多

   第一次动的时候，可以动最左或最右的石子

   贪心地吃掉所有的距离，但以下两个只能二选一：

• 最左到第二左的石子之间的距离

• 最右到第二右的石子之间的距离

  ****剩下的间隙我们可以统统吃掉。****多举些例子，可以发现这个规律。

  在纸上比划一下，可得到

  high = Math.max(A[n - 1] - n + 2 - A[1], A[n - 2] - A[0] - n + 2);

1. 最少

   这个我觉得简直是不可能人类能完美做出的解法

   要找到一个区间i …j 把所有的数能扔进去(或者放在连续的两侧)

   所以a[j] - a[i] +1 不能大于n（大于n就不行了，肯定会有空位）

   但还有种特殊情况，如1,2,3,4,10, 区间1-4里已经是连续了，你塞不进去

   这种情况只能是2， 先1->6, 再10->5

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); //还是要Min一下的，有可能为0， 或者1
            else
                low = Math.min(low, n - (j - i + 1));//这个区间是符合要求的，里面的j-i+1的数不用动，剩下的数要需要动的
        }
        return new int[] {low, high};
    }