Show problems as
Classic problem #907MediumArrayDynamic ProgrammingStackMonotonic Stack

Sum of Subarray Minimums

Real-world version: Weakest Reading Per Stretch
Tracked in this browser only
Read Sum of Subarray Minimums on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pipeline carries gauges at consecutive pumping stations. readings[i] is the pressure the gauge at station i reports.

A stretch is any block of one or more neighbouring stations. What a stretch can push through is set by its weakest gauge, so a stretch is rated at the smallest reading inside it. A pipeline of n stations therefore has n * (n + 1) / 2 stretches, each with its own rating.

Add together the ratings of all the stretches. The figure climbs fast, so give it as a remainder modulo 10^9 + 7.

Examples

Example 1

Input
readings = [4, 2, 3, 6]
Output
28

The four single stations are rated 4, 2, 3 and 6, the three pairs are rated 2, 2 and 3, the two triples are rated 2 and 2, and the whole line is rated 2, which adds to 28.

Example 2

Input
readings = [2, 2]
Output
6

Each station on its own is rated 2, and the stretch holding both of them is rated 2 as well, giving 6.

Example 3

Input
readings = [5]
Output
5

A single station forms one stretch, and its rating is its own reading.

Constraints

  • 1 <= readings.length <= 3 * 10^4
  • 1 <= readings[i] <= 3 * 10^4
  • Return the total modulo 10^9 + 7

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def total_stretch_minimums(readings: list[int]) -> int:
Java
public int totalStretchMinimums(int[] readings)

More on the same topics