Standard Bar Stack and Queues · Monotonic Stack and Queue O(n) · O(n)
A data pipeline processes every contiguous chunk of a job queue, and each chunk runs as slow as its least-capacity worker. Operations wants one number: the sum of the bottleneck capacities over all possible chunks. Duplicate capacities are allowed, so identical values in different positions still count as separate chunk configurations.
Input: An integer array arr of worker capacities.
Output: Return the sum of min(b) over every contiguous subarray b of arr, modulo 10^9 + 7.
1 <= arr.length <= 3 * 10^40 <= arr[i] <= 3 * 10^4Input: {"arr":[3,1,2,4]}
Output: 17
Single elements sum to 3+1+2+4=10; larger chunks add 1+1+2+1+2+1=7 more.
Input: {"arr":[11,81,94,43,3]}
Output: 444
Each element contributes its value times the count of chunks where it is the minimum.