Sum of Subarray Ranges
Medium · monotonic-stack
You are given a list of integers nums. A subarray is a non-empty run of neighbouring elements, such as nums[2..5]. Two subarrays are different if they start or end at different positions, even when they hold the same values.
The range of a subarray is its largest value minus its smallest value. A subarray with one element has range 0.
Return the sum of the ranges of all subarrays of nums.
Examples
Example 1
Input: nums = [1, 3, 2]
Output: 5
The single elements have range 0. The pairs [1, 3] and [3, 2] have ranges 2 and 1, and the whole list [1, 3, 2] has range 3 - 1 = 2. The total is 0 + 2 + 1 + 2 = 5.
Example 2
Input: nums = [4, 4, 4]
Output: 0
Every subarray holds equal values, so every range is 0.
Example 3
Input: nums = [-2, 5]
Output: 7
Only [-2, 5] has a non-zero range: 5 - (-2) = 7.
Constraints
- 1 <= len(nums) <= 10^5
- -10^4 <= nums[i] <= 10^4