Longest Non-Decreasing Subarray After Replacing at Most One Element
Real-world version: Longest Settled Pylon StretchThe statement here is our own: the same inputs, outputs and technique.
A cable crew surveys the pylons of a ski lift from the bottom station upward. Pylon i sits at height[i], measured in centimetres against a survey datum, so a pylon below the datum has a negative height.
A run of consecutive pylons is settled when the heights never drop as you walk it upward: for every neighbouring pair in the run, the later pylon is at least as high as the earlier one. Two pylons at exactly the same height are fine.
Before the survey is signed off, the crew may regrade at most one pylon: pick a single index and change height[i] to any integer you like, positive or negative, with no restriction to the heights already recorded. Every other pylon keeps its height.
Return the greatest number of pylons in a settled run of consecutive pylons that the crew can end up with. Regrading is optional, so a line that is already settled from end to end needs no change.
Examples
Example 1
- Input
- height = [-3, 4, -1, 6, 6]
- Output
- 5
Regrading pylon 1 to -2 leaves the heights -3, -2, -1, 6, 6, which never drop, so the whole line of 5 pylons is settled.
Example 2
- Input
- height = [-5, 8, -4, 7, -6, 2]
- Output
- 4
Regrading pylon 1 to -5 leaves the heights -5, -5, -4, 7, -6, 2. Pylons 0 through 3 read -5, -5, -4, 7 with no drop, a settled run of 4 pylons.
Example 3
- Input
- height = [-7, -7, 0, 5]
- Output
- 4
The recorded heights -7, -7, 0, 5 never drop as they stand, so all 4 pylons are already one settled run and the crew regrades nothing.
Constraints
- 1 <= height.length <= 10^5
- -10^9 <= height[i] <= 10^9
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.
def longest_settled_stretch(height: list[int]) -> int:public int longestSettledStretch(int[] height)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 18 test cases: 18 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's