主題
題目連結：
題目意譯：
你有 n 個機器人。你被給定兩個索引值從 0 開始的整數陣列 chargeTimes 和 runningCosts，兩者的長度都是 n。第 i 個機器人花費 chargeTimes[i] 單位來充電，且花費 runningCosts[i] 單位來運作。你同時也被給定一個整數 budget。
讓選出來的 k 個機器人運作之總成本定義為 max(chargeTimes) + k × sum(runningCosts)，其中 max(chargeTimes) 為 k 個機器人中最大的充電成本，而 sum(runningCosts) 為 k 個機器人中運作成本的總和。
回傳你最大可以同時運作的連續一群機器人（譯注：意即這些機器人盡可能地靠在一起），使得總成本不超過 budget。
限制：
chargeTimes.length == runningCosts.length == n
1 ≦ n ≦ 5 × 10 ^ 4
1 ≦ chargeTimes[i], runningCosts[i] ≦ 10 ^ 5
1 ≦ budget ≦ 10 ^ 15
範例測資：
範例 1：
輸入： chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
輸出： 3
解釋：
每個機器人自身以及每個相鄰機器人對都可以在成本內運作
為了得到答案 3，考慮前 3 個機器人。總成本將會是 max(3,6,1) + 3 × sum(2,1,3) = 6 + 3 × 6 = 24，其值小於 25。
可以證明不可能在成本內使 3 個以上的連續機器人同時運作，所以我們回傳 3。
範例 2：
輸入： chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
輸出： 0
解釋： 沒有機器人可以在不超過 budget 下運作，所以我們回傳 0。
解題思維：
考慮每個位置 i，其最左可以包含到哪（稱其位置 x，其中 0 ≦ x ≦ i），使得機器人 x 、 x + 1 、……、 i 同時運行的成本不超過 budget（如果連機器人 i 本身的成本都超過，則把 x 當作 i + 1）。
如果我們知道這樣子的資訊，則我們只要為每個位置 i 算出 (i - x + 1) 之值，便可以知道以機器人 i 作為連續機器人群集的結尾最多可以同時運行幾個機器人。而取出其中的最大值即為所求。
那麼每個相鄰位置（如 i 與 i + 1）之間的 x 值有所關聯嗎？總和這邊太單純了，就算 x 值之間毫無關聯，也可以輕鬆地用前綴和（Prefix Sums，如這題）解決。
那最大值呢？先假設我們知道位置 i 的區間 [x, i] 這些機器人中的 chargeTimes 最大值。可以推出位置 i + 1 的 x 值嗎？
答案是可以的。只要把位置 i + 1 這個機器人丟進 [x, i] 這個區間，然後「想辦法」得到新的最大值（稱其為 M）。然後計算出 M + ((i + 1) - x + 1) × 「[x, i + 1] 區間中的機器人 runningCosts 總和」是否超過 budget。
如果沒有超過，則兩個位置的 x 值相同；反之，則我們可以試著把位置 i 的 x 值加 1，然後看是否有小於等於 budget，如果沒有就繼續加 1 直到符合為止。「最後的 x 值」即為位置 i + 1 的 x 值。
所以問題變成了：上面敘述中間的「想辦法」是哪個辦法？答案是這題，利用雙端佇列（Deque）來維護一個區間中的最大值（藉由維護佇列中的數值非遞增性）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
