429. Sum of Stretch Ranges
A river gauge records the water level once per day in nums. For any run of consecutive days, its spread is the highest level in that run minus the lowest level in it, so a single day has spread 0. The engineers want the sum of the spreads over every possible run of one or more consecutive days.
Runs are distinguished by where they start and end, so equal values at different places make different runs. Return the total as a 64-bit integer. With up to 100,000 recordings there are billions of runs, so checking each run one by one will not finish in time; a smarter way to attribute each value to the runs where it is the maximum or the minimum is needed.
Example 1
- Input:
- nums = [4,1,6]
- Output:
- 13
- Explanation:
Runs: the singles give 0; 4,1 gives 3; 1,6 gives 5; the whole run gives 5. The total is 13.
Example 2
- Input:
- nums = [9,2,9,2]
- Output:
- 42
- Explanation:
Pairs give 7, 7, 7; triples give 7, 7; the full run gives 7; singles give 0, so the total is 42.
Constraints
1 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)