517. 超級洗衣機
假設有 n 台超級洗衣機放在同一排上。開始的時候,每台洗衣機内可能有一定量的衣服,也可能是空的。
在每一步操作中,你可以選擇任意 m (1 ≤ m ≤ n) 台洗衣機,與此同時将每台洗衣機的一件衣服送到相鄰的一台洗衣機。
給定一個非負整數數組代表從左至右每台洗衣機中的衣物數量,請給出能讓所有洗衣機中剩下的衣物的數量相等的最少的操作步數。如果不能使每台洗衣機中衣物的數量相等,則傳回 -1。
示例 1:
輸入: [1,0,5]
輸出: 3
解釋:
第一步: 1 0 <-- 5 => 1 1 4
第二步: 1 <-- 1 <-- 4 => 2 1 3
第三步: 2 1 <-- 3 => 2 2 2
示例 2:
輸入: [0,3,0]
輸出: 2
解釋:
第一步: 0 <-- 3 0 => 1 2 0
第二步: 1 2 --> 0 => 1 1 1
示例 3:
輸入: [0,2,0]
輸出: -1
解釋:
不可能讓所有三個洗衣機同時剩下相同數量的衣物。
提示:
n 的範圍是 [1, 10000]。
在每台超級洗衣機中,衣物數量的範圍是 [0, 1e5]。
PS:
我移動的最小的次數,無非來源于兩種
我目前值和平均值的差
我前面差的和
class Solution {
public int findMinMoves(int[] machines) {
int sum = 0;
for(int num : machines)
sum += num;
if(sum % machines.length != 0)
return -1;
int target = sum / machines.length;
int res = 0, balance = 0;
for(int i = 0 ; i < machines.length; i ++){
balance += machines[i] - target;
res = Math.max(res, Math.max(machines[i] - target, Math.abs(balance)));
}
return res;
}
}