A hiker starts at sea level (altitude 0) and takes steps whose altitude changes are listed in steps. A valley starts when the altitude goes from at least 0 to below 0 and ends when the altitude returns to at least 0. Return the number of completed valleys.
Examples
Input: steps = [-1, 1, -1, -1, 1, 1]
Output: 2
Explanation: Altitudes -1, 0, -1, -2, -1, 0 - two dips below sea level, both completed.
Input: steps = [1, -1, 1, -1]
Output: 0
Explanation: The hiker only climbs mountains.
Input: steps = [-2, 1, 3, -1, -1, 2]
Output: 1
Constraints
0 <= len(steps) <= 10**5-10 <= steps[i] <= 10- Target: O(n) time, O(1) extra space.
Goals
- Maintain a running altitude
- Detect transitions across a threshold rather than the values themselves