主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始並由 n 個正整數組成的陣列，以及一個正整數 k。
陣列 arr 如果 arr[i - k] ≦ arr[i] 對於每個索引值 i 都符合，其中 k ≦ i ≦ n - 1，則會稱為 K-遞增。
例如，arr = [4, 1, 5, 2, 6, 2] 對於 k = 2 時為 K-遞增，因為
arr[0] ≦ arr[2] (4 ≦ 5)
arr[1] ≦ arr[3] (1 ≦ 2)
arr[2] ≦ arr[4] (5 ≦ 6)
arr[3] ≦ arr[5] (2 ≦ 2)
不過在同一個 arr 下，對於 k = 1（arr[0] > arr[1]）以及 k = 3（arr[0] > arr[3]）則不是 K-遞增的。
在一次操作中，你可以選擇一個索引值 i 並將 arr[i] 變成任意正整數。
回傳對於給定的 k 值，最少所需之操作來讓該陣列變為 K-遞增。
限制：
1 ≦ arr.length ≦ 10 ^ 5
1 ≦ arr[i], k ≦ arr.length
範例測資：
範例 1：
輸入： arr = [5,4,3,2,1], k = 1
輸出： 4
解釋：
對於 k = 1，結果陣列需要是非遞減的。
其中有些 K-遞增陣列可以被產生出來，如 [5,6,7,8,9] 、 [1,1,1,1,1] 、 [2,2,3,4,4]。全部皆需要 4 次操作。
而將其改變成，例如 [6,7,8,9,10]，將不是最佳的方式，因為它會需要 5 次的操作。
可以證明我們不可能在少於 4 次操作下把陣列變成 K-遞增。
範例 2：
輸入： arr = [4,1,5,2,6,2], k = 2
輸出： 0
解釋：
本例與題目敘述中的那一個例子相同。
其中，對於每個索引值 i 都滿足 arr[i - 2] ≦ arr[i]，其中 2 ≦ i ≦ 5。
由於給定的陣列已經是 K-遞增了，因此不需要再做額外的操作。
範例 3：
輸入： arr = [4,1,5,2,6,2], k = 3
輸出： 2
解釋：
索引值 3 和 5 唯二沒有符合 arr[i - 3] ≦ arr[i]（對於 3 ≦ i ≦ 5）的位置。
將陣列變為 K-遞增的方式之一為把 arr[3] 變為 4、 arr[5] 變為 5。
陣列現在將變成 [4,1,5,4,6,5]。
注意到存在其他的方式可以把陣列變成 K-遞增，但是沒有任何一個需要少於 2 次的操作。
解題思維：
對於給定的 k 值，我們可以把 arr 分成以下若干個群組：
arr[0]、arr[k]、arr[2k]、……；
arr[1]、arr[k + 1]、arr[2k + 1]、……；
arr[2]、arr[k + 2]、arr[2k + 2]、……；
……
arr[k - 1]、arr[2k - 1]、arr[3k - 1]、……
其中當我們修改同一群組中的數值時，並不會影響到其他群組的大小關係。
因此，我們的所求可以改寫成「所有群組各自變成非遞減數列最少所需要的操作數之總和」。那要怎麼用最少的操作數來使某個群組變成非遞減呢？很簡單，我們只要在該群組中找出最長遞增子序列（Longest Increasing Subsequence，LIS）即可。
例如說現有一群組為 1 、 3 、 5 、 8 、 2 、 6 、 7，其最長遞增子序列為 1 、 3 、 5 、 6 、 7。可以看到剩下的兩個數字 8 和 2 位於數字 5 和數字 6 之間，此時只需要將這兩個數字變成 5 或是 6，則可以使這個群組滿足所需條件（非遞減）。而這樣子做將只需要最少的操作數。
而如果有多個最長遞增子序列的話也沒關係（假設長度為 X，且群組長度為 G），最少操作數將都會是 G - X 次操作。因此只需要關心最長遞增子序列的長度，此時便可以使用這題的策略來在 O(G log(G)) 的時間複雜度找到最長遞增子序列之長度 X。
最後將每個群組算出來的操作數加總，即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
