430. Sum of Stretch Minimums
A weather station stores one temperature reading per hour in nums. A stretch is any run of one or more consecutive hours, and every stretch is scored by the coldest reading inside it. An analyst wants the total of these scores over all stretches, counted separately by their position (the same values at two different places are two different stretches).
Return that total modulo 1_000_000_007, that is, modulo 10^9 + 7. A series of length n has n * (n + 1) / 2 stretches, so with up to 100,000 readings a nested loop over all stretches is far too slow. Readings are non-negative integers.
Example 1
- Input:
- nums = [5,2,6,3]
- Output:
- 29
- Explanation:
Stretches: 5,2,6,3 alone give 16; pairs give 2,2,3; triples give 2,2; the full run gives 2. The grand total is 16 + 7 + 4 + 2 = 29.
Example 2
- Input:
- nums = [7,7,1]
- Output:
- 24
- Explanation:
Singles give 15, the pairs 7-7 and 7-1 give 7 and 1, and the whole series gives 1, so the total is 24.
Constraints
1 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 3 * 104
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,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)