Skip to main content

1526. Minimum Number of Increments on Subarrays to Form a Target Array

Hard
Description

You are given an integer array target. You have an integer array initial of the same size as target with all elements initially zeros.

In one operation you can choose any subarray from initial and increment each value by one.

Return the minimum number of operations to form a target array from initial.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:​

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:​

Input: target = [3,1,1,2]
Output: 4
Explanation: [0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2]

Example 3:​

Input: target = [3,1,5,4,2]
Output: 7
Explanation: [0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] -> [3,1,2,2,2] -> [3,1,3,3,2] ->
[3,1,4,4,2] -> [3,1,5,4,2].

Constraints:​

  • 1 ≤\leq target.length ≤\leq 10510^5
  • 1 ≤\leq target[i] ≤\leq 10510^5

解題思路​

可以把這題目想成疊積木，像這張從詳解偷來的圖所示（點圖片可以連到原討論串）　　

這張圖是把 [3, 1, 5, 4, 2, 3, 4, 2] 轉換而成的圖，第一直排是 3 格高，第二是 1，以此類推
而紅色的邊數量總數就是這題的答案
因此可以先從最左邊的直排開始，先把初始值記錄起來

let result = target[0];

也就是先處理第一個直排，轉換成圖片就會像這樣：

而因為在完成第一直排的時候，最底下那排已經被一併完成了
故第二層開始時可以不必從 0，可以從第一層開始
且因第二直排是 1，故不必做任何事。 第三直排也同樣不必從 0 開始，可以從 1 開始疊

第四、五直排因為完成三的同時已經被完成了故跳過

後面也同理，完整步驟會長這樣

根據上面所式，如果新的直排比前一直排矮，代表他已經在疊前排時候被完成了，故可以跳過他
轉換成程式碼就會變成

for (let i = 1; i < target.length; i++) {
  // 從 1 開始是因為 target[0] 初始已被計算
  if (target[i] - target[i - 1] > 0) {
    // 如果 i 比前一排 i - 1 還小的話 result 不用增加，像第二排的 1 已經在上一步被完成了
    result += target[i] - target[i - 1];
    // 較大的話僅增加兩者的差異值
    // 如圖片 4 ~ 7 步驟是 1 , 5 的話增加 4，因為 1 已經在上一步先加上了
  }
}

最後遍歷完一遍就是答案了 !

return result;

心得​

謝謝 Neetcode 解釋這題