題目

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.

題目大意

在一個長度無限的數軸上，第 i 顆石子的位置為 stones[i]。如果一顆石子的位置最小/最大，那麼該石子被稱作端點石子。每個回合，你可以將一顆端點石子拿起並移動到一個未佔用的位置，使得該石子不再是一顆端點石子。值得注意的是，如果石子像 stones = [1,2,5] 這樣，你將無法移動位於位置 5 的端點石子，因為無論將它移動到任何位置（例如 0 或 3），該石子都仍然會是端點石子。當你無法進行任何移動時，即，這些石子的位置連續時，遊戲結束。

要使遊戲結束，你可以執行的最小和最大移動次數分別是多少？ 以長度為 2 的數組形式返回答案：answer = [minimum\_moves, maximum\_moves] 。

提示：

1. 3 <= stones.length <= 10^4
2. 1 <= stones[i] <= 10^9
3. stones[i] 的值各不相同。

解題思路

• 給出一個數組，數組裏面代表的是石頭的座標。要求移動石頭，最終使得這些石頭的座標是一個連續的自然數列。但是規定，當一個石頭是端點的時候，是不能移動的，例如 [1,2,5]，5 是端點，不能把 5 移到 3 或者 0 的位置，因為移動之後，這個石頭仍然是端點。最終輸出將所有石頭排成連續的自然數列所需的最小步數和最大步數。
• 這道題的關鍵就是如何保證端點石頭不能再次移動到端點的限制。例如，[5,6,8,9,20]，20 是端點，但是 20 就可以移動到 7 的位置，最終形成 [5,6,7,8,9] 的連續序列。但是 [5,6,7,8,20]，這種情況 20 就不能移動到 9 了，只能讓 8 移動到 9，20 再移動到 8 的位置，最終還是形成了 [5,6,7,8,9]，但是步數需要 2 步。經過上述分析，可以得到，端點石頭只能往中間空擋的位置移動，如果中間沒有空擋，那麼需要藉助一個石頭先製造一個空擋，然後端點石頭再插入到中間，這樣最少是需要 2 步。
• 再來考慮極值的情況。先看最大步數，最大步數肯定慢慢移動，一次移動一格，並且移動的格數最多。這裏有兩個極端情況，把數組裏面的數全部都移動到最左端點，把數組裏面的數全部都移動到最右端點。每次只移動一格。例如，全部都移到最右端點：

[3,4,5,6,10] // 初始狀態，連續的情況
  [4,5,6,7,10] // 第一步，把 3 挪到右邊第一個可以插入的位置，即 7
  [5,6,7,8,10] // 第二步，把 4 挪到右邊第一個可以插入的位置，即 8
  [6,7,8,9,10] // 第三步，把 5 挪到右邊第一個可以插入的位置，即 9
  
  
  [1,3,5,7,10] // 初始狀態，不連續的情況
  [3,4,5,7,10] // 第一步，把 1 挪到右邊第一個可以插入的位置，即 4
  [4,5,6,7,10] // 第二步，把 3 挪到右邊第一個可以插入的位置，即 6
  [5,6,7,8,10] // 第三步，把 4 挪到右邊第一個可以插入的位置，即 8
  [6,7,8,9,10] // 第四步，把 5 挪到右邊第一個可以插入的位置，即 9

挪動的過程類似翻滾，最左邊的石頭挪到右邊第一個可以放下的地方。然後不斷的往右翻滾。把數組中的數全部都移動到最左邊也同理。對比這兩種情況的最大值，即是移動的最大步數。

• 再看最小步數。這裏就涉及到了滑動窗口了。由於最終是要形成連續的自然數列，所以滑動窗口的大小已經固定成 n 了，從數組的 0 下標可以往右滑動窗口，這個窗口中能包含的數字越多，代表窗口外的數字越少，那麼把這些數字放進窗口內的步數也最小。於是可以求得最小步數。這裏有一個比較坑的地方就是題目中的那個“端點不能移動以後還是端點”的限制。針對這種情況，需要額外的判斷。如果當前窗口內有 n-1 個元素了，即只有一個端點在窗口外，並且窗口右邊界的值減去左邊界的值也等於 n-1，代表這個窗口內已經都是連續數字了。這種情況端點想融合到這個連續數列中，最少需要 2 步(上文已經分析過了)。
• 注意一些邊界情況。如果窗口從左往右滑動，窗口右邊界滑到最右邊了，但是窗口右邊界的數字減去左邊界的數字還是小於窗口大小 n，代表已經滑到頭了，可以直接 break 出去。為什麼滑到頭了呢？由於數組經過從小到大排序以後，數字越往右邊越大，當前數字是小值，已經滿足了 stones[right]-stones[left] < n，左邊界繼續往右移動只會使得 stones[left] 更大，就更加小於 n 了。而我們需要尋找的是 stones[right]-stones[left] >= n 的邊界點，肯定再也找不到了。

參考代碼

package leetcode

import (
	"math"
	"sort"
)

func numMovesStonesII(stones []int) []int {
	if len(stones) == 0 {
		return []int{0, 0}
	}
	sort.Ints(stones)
	n := len(stones)
	maxStep, minStep, left, right := max(stones[n-1]-stones[1]-n+2, stones[n-2]-stones[0]-n+2), math.MaxInt64, 0, 0
	for left < n {
		if right+1 < n && stones[right]-stones[left] < n {
			right++
		} else {
			if stones[right]-stones[left] >= n {
				right--
			}
			if right-left+1 == n-1 && stones[right]-stones[left]+1 == n-1 {
				minStep = min(minStep, 2)
			} else {
				minStep = min(minStep, n-(right-left+1))
			}
			if right == n-1 && stones[right]-stones[left] < n {
				break
			}
			left++
		}
	}
	return []int{minStep, maxStep}
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}