Sorted Fence Heights
A row of fence sections has given heights. Increase their heights so that they become non-decreasing from left to right.
In one operation, choose any non-empty consecutive group of fence sections and increase every selected height by the same positive integer x. The cost of this operation is x, regardless of how many sections are selected.
Return the minimum total cost required to make the fence heights non-decreasing.
Minimum Fence Increase
Implement the following method:
long minimumFenceIncrease(List<Integer> fenceHeights)
The parameter fenceHeights contains the initial heights of the fence sections from left to right.
Return the minimum sum of the operation costs needed to arrange the heights in non-decreasing order.
Behavior Requirements
- Each operation must select one or more consecutive fence sections.
- The same positive integer
x must be added to every selected height.
- The cost of an operation is
x, not x multiplied by the number of selected sections.
- Any number of operations may be performed, including zero operations.
- In the final arrangement,
fenceHeights.get(i) ≤ fenceHeights.get(i + 1) must hold for every valid index i.
Constraints
1 ≤ fenceHeights.size() ≤ 100,0001 ≤ fenceHeights.get(i) ≤ 1,000,000,0000 ≤ i < fenceHeights.size()- The result fits in a Java
long.
Examples
Example 1
minimumFenceIncrease(fenceHeights = [4, 1, 3, 2])
Output: 4
Increase the final three sections by 3 to obtain [4, 4, 6, 5]. Then increase the final section by 1 to obtain [4, 4, 6, 6]. The total cost is 3 + 1 = 4.
Example 2
minimumFenceIncrease(fenceHeights = [2, 2, 5, 8])
Output: 0
The heights are already non-decreasing, so no operation is required.
Example 3
minimumFenceIncrease(fenceHeights = [9, 7, 4, 1])
Output: 8
The three decreases have sizes 2, 3, and 3. They can be corrected using consecutive groups with a minimum total cost of 8.
Example 4
minimumFenceIncrease(fenceHeights = [12])
Output: 0
A single fence section is always non-decreasing.