Stretches Framed by Peaks

Hard

Points along a mountain ridge are listed in order, and their heights are stored in the array heights. Call a contiguous stretch heights[l..r] (with l ≤ r) good if its first and last points both have the greatest height in that stretch. In other words, heights[l] == heights[r] and no point between them is higher. Return the number of good stretches. A stretch of a single point counts too.

Example 1

heights=[2, 5, 1, 5, 3] → 6

All 5 single-point stretches count, plus [5, 1, 5]: both ends are 5 and nothing in between is higher. 6 in total.

Example 2

heights=[4, 4, 4] → 6

Every one of the 6 stretches counts, since all heights are equal.

Example 3

heights=[3, 7, 3] → 3

The stretch [3, 7, 3] fails because the 7 inside is higher than its ends. Only the 3 single-point stretches remain.

Constraints

1 ≤ len(heights) ≤ 10⁵
1 ≤ heights[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Array Binary Search Monotonic Stack

Similar problems

Widest Fence Span Around the Marked Board Hard Second Larger to the Right Hard Best Pair Above the Bars Hard First Common Rooftop Hard Most Blocks After Merging Hard

Input

heights=[2, 5, 1, 5, 3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.