對數(shù)組執(zhí)行操作

【原地賦值】按題意模擬，原地操作O(1)空間。

長度為 K 子數(shù)組中的最大和

【哈希表 + 滑動窗口】不能每劃一次就重新計算一遍會TLE，先把k-1個元素加到窗口里，然后開始滑。

雇傭 K 位工人的總代價

【兩個最小堆】讀題，找到合適的數(shù)據(jù)結(jié)構(gòu)，維護一些數(shù)字中的最小值、需要去掉最小值、需要加入元素 —→ 堆。如果前后的candidates元素重疊，直接對costs排序取剩余的k個數(shù)。代碼中，i指向前c的下一個待加入元素，指向后c的前一個待加入元素，必須i ≤ j表示沒重疊，如果i > j可以把pre和suf拼起來當(dāng)作costs。 相當(dāng)于把一開始就重疊和操作后的重疊的兩種情況合在一起。[python切片有拷貝，空間復(fù)雜度是O(n)，go是O(1)，當(dāng)然也可以用itertools.islice實現(xiàn)O(1)，不過不能傳入heapify。最后的排序+切片，也可以快速選擇求前k小，時間復(fù)雜度為O(n)，]

最小移動總距離

【記憶化搜索】用鄰項交換法可以證明，對機器人和工廠按照位置從小到大排序，那么每個工廠修復(fù)的機器人就是連續(xù)的一段了。原問題：n個工廠修m個機器人，子問題：枚舉第一個工廠修了x個機器人，轉(zhuǎn)換成n-1個工廠修了m-x個機器人。定義f(i,j)表示用第i個及其右側(cè)的工廠，修理第j個及其右側(cè)的機器人，機器人移動的最小總距離，f(i,j) = min(f(i + 1, k + 1) + cost(i, j , k))，這里cost(i,j,k)表示第i個工廠修復(fù)從j到k的機器人，移動距離就是這些機器人到第i個工廠的距離之和。（k-j+1≤limit[i]）

【遞推 + 空間壓縮】遞推比記憶化搜索省空間（遞歸損耗，以及python內(nèi)置哈希表實現(xiàn)記憶化，用數(shù)組會快點。記憶化搜索通過剪枝優(yōu)化，遞推用數(shù)據(jù)結(jié)構(gòu)優(yōu)化轉(zhuǎn)移/壓縮空間）。定義f[i] [j] 為前i個工廠修復(fù)前j個機器人的最小移動總距離。代碼實現(xiàn)時，第一個維度可以像01背包那樣優(yōu)化掉。