另外開個陣列紀錄每個數字的位置,接著從數字1跑到倒數第2個數字,當有個數字 x 的位置 loc[x] 和他前一個數字loc[x-1]位置差乘 (loc[x+1] - loc[x]) 小於0代表要更換方向,這方法錯在哪裡?甘溫 

可以試著把存數字的陣列之型態改成 long long ，避免作乘法時溢位。不過有方法不需要乘法，以下提供本人的想法：

以範例輸入二為例，我們將數值由小到大排序，並保留原有的索引值（原本在數列的位置）：

1 3 5 2 4　←　索引值

1 2 3 4 5　←　本身的數值

可以看到一開始狗狗由左往右跑，因此索引值是遞增的，所以 1 、 3 、 5 都會被移除掉。

再來，狗狗改變了方向，使得索引值會遞減。如此，只會拿到 4 。最後，再次改變方向，拿到了 5 。以上，狗狗改變了 2 次方向，因此輸出「2」。

因此，我們可以看到：把數值排序好後。一開始索引值應該要遞增，但是一遇到比現在的索引值還小的，就要改變為遞減；反之，遞減的時候遇到比現在還大的索引值，則改為遞增。

而遞增以及遞減的變換次數，即為狗狗變換方向的次數。

以上。希望能幫到您。