在 X 軸上有一些不同位置的石子。給定一個整數數組 stones 表示石子的位置。

如果一個石子在最小或最大的位置，稱其為 端點石子。每個回合，你可以將一顆 端點石子 拿起并移動到一個未占用的位置，使得該石子不再是一顆 端點石子。

值得注意的是，如果石子像 stones = [1,2,5] 這樣，你將 無法 移動位于位置 5 的端點石子，因為無論將它移動到任何位置（例如 0 或 3），該石子都仍然會是端點石子。
當你無法進行任何移動時，即，這些石子的位置連續時，游戲結束。

以長度為 2 的數組形式返回答案，其中：

answer[0] 是你可以移動的最小次數
answer[1] 是你可以移動的最大次數。

示例 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 <= stones.length <= 104
1 <= stones[i] <= 109
stones 的值各不相同。

解：由于我們每次移動只能將兩端的石子移動到中間，因此每次移動必定使得石子更加密集。

先定義石子的最大距離為stones[n-1]-stones[0]，對于最大值，我們應該每次移動都使得石子的最大距離減小1，即像跳棋一樣，每次都將兩端的某個石子移動到距離自己最近的中間位置，如128，首先將位置1的石子移動到2后面，即238，然后再將位置2的石子移動到3后面，即348，同理，后面幾步為458、568、678，到678石子就連續了，這種方式每一步使得石子的最大距離都減少了1，移動總步數最大，值為初始情況下兩端石子的中間空閑位置的數量，即5。但對于第一步來說，并不總能使石子的最大距離減小1，如137，移動方式一是把7移到13中間，則石子的最大距離縮小了4；方式二則是把1移動到37中間，則石子的最大距離縮小了2；我們應該選擇縮小距離較短的方式二。第一步之后，就可以有方法使每次移動距離都只縮小1了。因此最大值的公式為：

$$max(stones[n?2]?stones[0],stones[n?1]?stones[0])?1?(n?3)$$

公式解釋：max選出第一步移動時，使距離縮小較短的方式。對于第一步移動右端石子的情況，記stone為s，開區間(s[0], s[n-2])中間有s[n-2] - s[0] - 1個位置，去掉s[0]、s[n-2]、s[n-1]，剩下的n-3個石子占用了這些位置，因此空閑位置數量就是s[n-2] - s[0] - 1 - (n - 3)。對于第一步移動左端石子的情況，同理。

對于最小值，我們可以用滑窗解決，如果有n個石子，我們維護一個n個石子的窗口，看其中有多少個空閑位置，空閑位置數即為移動石子的最小值。但有一種特殊情況，如1678，我們不能把1移動到5或9，因此特殊情況就是一個單獨石子+一串連續石子的情況。這種特殊情況的移動次數為2，只需把連續石子中8移動為4，然后再將1移動為5即可。

class Solution {
public:vector<int> numMovesStonesII(vector<int>& stones) {sort(stones.begin(), stones.end());int n = stones.size();int max1 = stones[n - 2] - stones[0] - n + 2;int max2 = stones[n - 1] - stones[1] - n + 2;int maxNum = max(max1, max2);// 如果是特殊情況if (max1 == 0 || max2 == 0) {// 保證最小值小于2return {min(maxNum, 2), maxNum};}int minNum = numeric_limits<int>::max();int left = 0;for (int i = 0; i < n; ++i) {while (stones[i] - stones[left] + 1 > n) {++left;}minNum = min(minNum, n - i + left - 1);}return {minNum, maxNum};}
};

如果有n個石子，則此算法時間復雜度為O(nlogn)，空間復雜度為O(1)。