A weather station logs one temperature reading per hour in the list temps. For a stretch of
consecutive hours, its spread is the highest reading in the stretch minus the lowest reading in
the stretch (a stretch of one hour has spread 0).
Return the total of the spreads of every non-empty stretch of consecutive hours. There are
n * (n + 1) / 2 stretches for n readings. Return 0 for an empty log.
Examples
Input: temps = [1, 3, 2]
Output: 5
Explanation: [1,3] has spread 2, [3,2] has 1, [1,3,2] has 2, single hours have 0.
Input: temps = [2, 2, 2]
Output: 0
Input: temps = [4, -1, 4]
Output: 15
Explanation: [4,-1], [-1,4] and [4,-1,4] each have spread 5.
Constraints
0 <= len(temps) <= 10**5-10**9 <= temps[i] <= 10**9- Target:
O(n)time; checking every stretch is far too slow for the largest logs
Goals
- Turn a sum over all stretches into a sum of per-element contributions
- Use a monotonic stack to find how far each reading stays the maximum or the minimum
- Break ties between equal readings so that no stretch is counted twice