Package g1501_1600.s1526_minimum_number_of_increments_on_subarrays_to_form_a_target_array

Class Solution

java.lang.Object

g1501_1600.s1526_minimum_number_of_increments_on_subarrays_to_form_a_target_array.Solution

public class Solution
extends Object

1526 - Minimum Number of Increments on Subarrays to Form a Target Array.<p>Hard</p> <p>You are given an integer array <code>target</code>. You have an integer array <code>initial</code> of the same size as <code>target</code> with all elements initially zeros.</p> <p>In one operation you can choose <strong>any</strong> subarray from <code>initial</code> and increment each value by one.</p> <p>Return <em>the minimum number of operations to form a</em> <code>target</code> <em>array from</em> <code>initial</code>.</p> <p>The test cases are generated so that the answer fits in a 32-bit integer.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> target = [1,2,3,2,1]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> We need at least 3 operations to form the target array from the initial array.</p> <p>[<strong>0,0,0,0,0</strong> ] increment 1 from index 0 to 4 (inclusive).</p> <p>[1, <strong>1,1,1</strong> ,1] increment 1 from index 1 to 3 (inclusive).</p> <p>[1,2, <strong>2</strong> ,2,1] increment 1 at index 2.</p> <p>[1,2,3,2,1] target array is formed.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> target = [3,1,1,2]</p> <p><strong>Output:</strong> 4</p> <p><strong>Explanation:</strong> [<strong>0,0,0,0</strong> ] -> [1,1,1, <strong>1</strong> ] -> [<strong>1</strong> ,1,1,2] -> [<strong>2</strong> ,1,1,2] -> [3,1,1,2]</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> target = [3,1,5,4,2]</p> <p><strong>Output:</strong> 7</p> <p><strong>Explanation:</strong> [<strong>0,0,0,0,0</strong> ] -> [<strong>1</strong> ,1,1,1,1] -> [<strong>2</strong> ,1,1,1,1] -> [3,1, <strong>1,1,1</strong> ] -> [3,1, <strong>2,2</strong> ,2] -> [3,1, <strong>3,3</strong> ,2] -> [3,1, <strong>4</strong> ,4,2] -> [3,1,5,4,2].</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= target.length <= 10⁵</code></li> <li><code>1 <= target[i] <= 10⁵</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minNumberOperations(int[] target)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minNumberOperations

public int minNumberOperations(int[] target)