#1959
Minimum Total Space Wasted With K Resizing Operations
specialist · 965 · lc medium +32 · failed · 43.9% accepted · 593 likes · top 26%
Description
You are designing a dynamic array. At each time step i, the array must hold at least nums[i] elements. You may resize the array at most k times (the initial size choice does not count). Wasted space at time i is size_i - nums[i].
Return the minimum total wasted space across all time steps.
Example 1:
Input: nums = [10,20], k = 0
Output: 10
Explanation: size = [20,20].
We can set the initial size to be 20.
The total wasted space is (20 - 10) + (20 - 20) = 10.
Example 2:
Input: nums = [10,20,30], k = 1
Output: 10
Explanation: size = [20,20,30].
We can set the initial size to be 20 and resize to 30 at time 2.
The total wasted space is (20 - 10) + (20 - 20) + (30 - 30) = 10.
Example 3:
Input: nums = [10,20,15,30,20], k = 2
Output: 15
Explanation: size = [10,20,20,30,30].
We can set the initial size to 10, resize to 20 at time 1, and resize to 30 at time 3.
The total wasted space is (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15.
Code
1
2
3