Standard Bar Stack and Queues · Monotonic Stack and Queue O(n) · O(n)
A delivery fleet logs vehicle loads in a row, and analysts define the 'spread' of any stretch of vehicles as its hottest load minus its coolest. Finance wants the grand total of spreads across every contiguous stretch. The audit runs twice: once summing maxima contributions, once subtracting minima contributions.
Input: An integer array nums of vehicle loads.
Output: Return the sum of (max - min) over every contiguous subarray of nums.
1 <= nums.length <= 1000-10^9 <= nums[i] <= 10^9Input: {"nums":[1,2,3]}
Output: 4
Ranges are 0,0,0 for singles, 1 and 1 for the pairs, and 2 for the full array: total 4.
Input: {"nums":[1,3,3]}
Output: 4
Duplicates count as separate positions; the pairs (1,3) contribute 2 each and the full array contributes 2.