LeetCode 解題紀錄 1033. Moving Stones Until Consecutive

Moving Stones Until Consecutive - LeetCode

題目

在 x 軸上有三顆石頭，將三顆石頭移動到連續的位置上所需最大與最小步數，一次可移動最左邊或最右邊的石頭到原本範圍內的任意位置

限制

• 石頭位置介於 1 ~ 100
• 三個石頭在不同位置

觀察

• 由於不能往外側移動，最大步數一定是一次移動一步，最多就是兩者的位置相減後再減 1
• 最少步數在一般狀況下為固定值 2，就是左右石頭分別移動到中間石頭的隔壁，除非遇到兩個 corner cases
• 1. 原本就在隔壁，移動步數為 0
• 2. 有兩個石頭間隔為 2，中間還有一個位置，移動步數為 1

思路

• 將輸入位置進行排序，方便利用索引來計算
• 最大值只要套用公式運算一次就可得到
• 最小值根據相對位置來判斷，選取三個值得其中一個

Trial 1

結果

因為排序的關係，時間複雜度為 O(n log n) 空間複雜度為 O(n)，因為 n 固定為 3，應可視為 O (1) ，這個問題很佛心的將 corner case 列在 example TC 裡，如果沒有列的話，我想應該 acceptance rate 應該會降低一些，須要多加留心