LeetCode 1040. Moving Stones Until Consecutive II【排序,滑动窗口,双指针】中等

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ls9tkdcC-1680920794971)(https://image-1307616428.cos.ap-beijing.myqcloud.com/Obsidian/202304071602714.png)]
There are some stones in different positions on the X-axis. You are given an integer array stones, the positions of the stones.

Call a stone an endpoint stone if it has the smallest or largest position. In one move, 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 (i.e., the stones are in three consecutive positions).

Return an integer array answer of length 2 where:

• answer[0] is the minimum number of moves you can play, and
• answer[1] is the maximum number of moves you can play.

Example 1:

Input: stones = [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: stones = [6,5,4,3,10]
Output: [2,3]
Explanation: 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.

Constraints:

• 3 <= stones.length <= 10^4
• 1 <= stones[i] <= 10^9
• All the values of stones are unique.

题意：X轴上一些石头在不同的位置。数组 stones 描述了这些石头的下标位置。如果一个石头有最小或最大的下标位置，则叫它端点 endpoint stone 。一次移动中，我们可以选择一个端点石头、并将它移动到一个空位置、使它不再是一个端点。无法进行更多移动时，游戏结束，返回数组 answer[2] ，answer[0] 表示能进行的最少移动次数，answer[1] 表示能移动的最多次数。

---

解法 排序+滑窗+同向双指针

题目的限制可以概括为两点：

1. 只能移动端点。
2. 端点移动后不能还是端点，且只能移动到空位上。

且移动后端点间距离一定会变小，除非游戏结束。如下所示，移动前端点距离为 6 6 6 ，移动后端点距离为 4 4 4 ：

由于 n ≥ 3 n \ge 3 n≥3 ，如果右边有空位，可以让左端点移过去；如果左边有空位，可以让右端点移过去。。

下面讨论怎样做到最大移动次数。显然，如果像老太太慢悠悠一步一步走路来移动，就能得到最大移动次数。即。但第一步可能无法这样移动、会多移动一点，还有一些情况下某个端点也无法做到这一点。比如下图，第一步要么 1 1 1 移动到 4 ∼ 6 4 \sim 6 4∼6（此后 1 1 1 不是端点），要么 7 7 7 移动到 2 2 2 （此后 7 7 7 不是端点）；显然， 7 7 7 移动到 2 2 2 ，后面就无法移动了； 1 1 1 移到 4 4 4 ，后面就可像下跳棋一样、借助后面的石头一步一步“跳”过去，从而多移动几次。

上图中移动的最大次数为 3 3 3 ，是通过不断移动左端点到 ( s [ 1 ] , s [ n − 1 ] ) (s[1], s[n-1]) (s[1],s[n−1]) 区间中的空位达成的。因此最大移动次数的结论（简记 s t o n e s stones stones 为 s s s ）：

这是什么意思？

• 要往左移动端点 s [ n − 1 ] s[n-1] s[n−1] ，由于移动后不能还让它是端点，就只能移到开区间 ( s [ 0 ] , s [ n − 2 ] ) (s[0], s[n-2]) (s[0],s[n−2]) 中，这一开区间中有 s [ n − 2 ] − s [ 0 ] − 1 s[n - 2] - s[0] - 1 s[n−2]−s[0]−1 个位置，去掉已知的三颗石头 s [ 0 ] , s [ n − 2 ] , s [ n − 1 ] s[0], s[n - 2], s[n-1] s[0],s[n−2],s[n−1] ，剩下还有 n − 3 n - 3 n−3 颗石头占有开区间中的位置，剩下的空位就是 s [ n − 2 ] − s [ 0 ] − 1 − ( n − 3 ) = s [ n − 2 ] − s [ 0 ] − n + 2 s[n - 2] - s[0] - 1- (n-3) = s[n - 2] - s[0] - n + 2 s[n−2]−s[0]−1−(n−3)=s[n−2]−s[0]−n+2 。
• 要往右移动端点 s [ 0 ] s[0] s[0] ，由于移动后不能还让它是端点，就只能移到开区间 ( s [ 1 ] , s [ n − 1 ] ) (s[1], s[n-1]) (s[1],s[n−1]) 中，这一开区间中有 s [ n − 1 ] − s [ 1 ] − 1 s[n - 1] - s[1] - 1 s[n−1]−s[1]−1 个位置，去掉已知的三颗石头 s [ n − 1 ] , s [ 0 ] , s [ 1 ] s[n-1], s[0], s[1] s[n−1],s[0],s[1] ，剩下还有 n − 3 n - 3 n−3 颗石头占有开区间中的位置，剩下的空位就是 s [ n − 1 ] − s [ 1 ] − 1 − ( n − 3 ) = s [ n − 1 ] − s [ 1 ] − n + 2 s[n - 1] - s[1] - 1 - (n-3) = s[n - 1] - s[1] - n + 2 s[n−1]−s[1]−1−(n−3)=s[n−1]−s[1]−n+2 。

下面讨论最小移动次数，既然端点可以移动到中间任意空位，那么将所有石头都一步到位就是最快的，最后 n n n 个石头形成数轴长为 n n n 的序列。于是问题转换为：。计算长度为 n n n 的窗口中最少有多少个空位，等价于 n n n 减去窗口内的最多石头个数。由于窗口滑动到下个石头前，窗口中的石头不会变多，就可以直接滑到下一颗石头。

从而最小移动次数的结论是：

特殊情况就是：下图中无法直接把 1 1 1 移到窗口中的空位 5 5 5 ，即第一步出现问题。为此需要先移动另外一个端点、将窗口改变，才能把 1 1 1 移动到 5 5 5 。

class Solution {
public:
   vector<int> numMovesStonesII(vector<int> &s) {
       sort(s.begin(), s.end());
       int n = s.size();
       int e1 = s[n - 2] - s[0] - n + 2;
       int e2 = s[n - 1] - s[1] - n + 2;
       int max_move = max(e1, e2);
       if (e1 == 0 || e2 == 0) // 特殊情况：没有空位
           return {min(2, max_move), max_move};
       int max_cnt = 0, left = 0;
       for (int right = 0; right < n; ++right) { // 滑动窗口：枚举右端点
           while (s[right] - s[left] + 1 > n) // 窗口大小大于 n
               ++left;
           max_cnt = max(max_cnt, right - left + 1); // 维护窗口内的最大石子数
       }
       return {n - max_cnt, max_move};
   }
};

复杂度分析

• 时间复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn) ，其中 n n n 为 s t o n e s stones stones 的长度。瓶颈在排序上。
• 空间复杂度： O ( 1 ) O(1) O(1) 。忽略排序时的栈开销，仅用到若干额外变量。

相似题目：

• 3.无重复字符的最长子串
• 209.长度最小的子数组
• 713.乘积小于 K 的子数组
• 1004.最大连续 1 的个数 III
• 1234.替换子串得到平衡字符串
• 1658.将 x 减到 0 的最小操作数