Longest Uphill Stretch

Medium

A weather station logs the river level once a day: levels[i] is the reading on day i. Call a pair of days i < j an *uphill stretch* if the water on day j is at least as high as on day i, that is, levels[i] ≤ levels[j]. The length of the stretch is j - i; whatever happened in between does not matter. Return the greatest length of an uphill stretch, or 0 if there is no such pair.

Example 1

levels=[4, 7, 1, 3, 2, 5] → 5

Day 0 has level 4 and day 5 has level 5: 4 ≤ 5, a distance of 5, the largest possible.

Example 2

levels=[9, 6, 2, 8, 3, 2] → 3

The best pair is days 2 and 5 (2 ≤ 2), a distance of 3. Day 0 has no partner at all, and day 1 only reaches the 8 on day 3, a distance of 2.

Example 3

levels=[5, 4, 3, 2] → 0

The levels only go down, so no pair qualifies and the answer is 0.

Constraints

2 ≤ len(levels) ≤ 5·10⁴
0 ≤ levels[i] ≤ 5·10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Array Two Pointers Monotonic Stack

Similar problems

Fix the Middle of the Line Medium Cut the Middle to Restore Order Medium Water Between Walls Hard Largest Number From Two Rows Hard Widest Fence Span Around the Marked Board Hard

Input

levels=[4, 7, 1, 3, 2, 5]

Expected

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