Skip to content

3738. Longest Non-Decreasing Subarray After Replacing at Most One Element

Description

You are given an integer array nums.

You are allowed to replace at most one element in the array with any other integer value of your choice.

Return the length of the longest non-decreasing subarray that can be obtained after performing at most one replacement.

An array is said to be non-decreasing if each element is greater than or equal to its previous one (if it exists).

 

Example 1:

Input: nums = [1,2,3,1,2]

Output: 4

Explanation:

Replacing nums[3] = 1 with 3 gives the array [1, 2, 3, 3, 2].

The longest non-decreasing subarray is [1, 2, 3, 3], which has a length of 4.

Example 2:

Input: nums = [2,2,2,2,2]

Output: 5

Explanation:

All elements in nums are equal, so it is already non-decreasing and the entire nums forms a subarray of length 5.

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109​​​​​​​

Solutions

Solution 1: Prefix and Suffix Decomposition + Enumeration

We can use two arrays \(\textit{left}\) and \(\textit{right}\) to record the length of the longest non-decreasing subarray ending and starting at each position, respectively. Initially, \(\textit{left}[i] = 1\) and \(\textit{right}[i] = 1\).

Then, we traverse the array in the range \([1, n-1]\). If \(\textit{nums}[i] \geq \textit{nums}[i-1]\), we update \(\textit{left}[i]\) to \(\textit{left}[i-1] + 1\). Similarly, we traverse the array backwards in the range \([n-2, 0]\). If \(\textit{nums}[i] \leq \textit{nums}[i+1]\), we update \(\textit{right}[i]\) to \(\textit{right}[i+1] + 1\).

Next, we can compute the final answer by enumerating each position. For each position \(i\), we can calculate the length of the longest non-decreasing subarray centered at \(i\) in the following way:

  1. If the elements on the left and right sides of \(i\) do not satisfy \(\textit{nums}[i-1] \leq \textit{nums}[i+1]\), we can only choose the non-decreasing subarray from either the left or right side, so the answer is \(\max(\textit{left}[i-1], \textit{right}[i+1]) + 1\).
  2. Otherwise, we can replace position \(i\) with an appropriate value so that the non-decreasing subarrays on the left and right can be connected, so the answer is \(\textit{left}[i-1] + \textit{right}[i+1] + 1\).

Finally, we take the maximum value across all positions as the final answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            if nums[i] >= nums[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if nums[i] <= nums[i + 1]:
                right[i] = right[i + 1] + 1
        ans = max(left)
        for i in range(n):
            a = 0 if i - 1 < 0 else left[i - 1]
            b = 0 if i + 1 >= n else right[i + 1]
            if i - 1 >= 0 and i + 1 < n and nums[i - 1] > nums[i + 1]:
                ans = max(ans, a + 1, b + 1)
            else:
                ans = max(ans, a + b + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        int ans = 1;

        for (int i = 1; i < n; i++) {
            if (nums[i] >= nums[i - 1]) {
                left[i] = left[i - 1] + 1;
                ans = Math.max(ans, left[i]);
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= nums[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }

        for (int i = 0; i < n; i++) {
            int a = (i - 1 < 0) ? 0 : left[i - 1];
            int b = (i + 1 >= n) ? 0 : right[i + 1];
            if (i - 1 >= 0 && i + 1 < n && nums[i - 1] > nums[i + 1]) {
                ans = Math.max(ans, Math.max(a + 1, b + 1));
            } else {
                ans = Math.max(ans, a + b + 1);
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 1), right(n, 1);

        for (int i = 1; i < n; ++i) {
            if (nums[i] >= nums[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] <= nums[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }

        int ans = ranges::max(left);

        for (int i = 0; i < n; ++i) {
            int a = (i - 1 < 0) ? 0 : left[i - 1];
            int b = (i + 1 >= n) ? 0 : right[i + 1];
            if (i - 1 >= 0 && i + 1 < n && nums[i - 1] > nums[i + 1]) {
                ans = max({ans, a + 1, b + 1});
            } else {
                ans = max(ans, a + b + 1);
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func longestSubarray(nums []int) int {
    n := len(nums)
    left := make([]int, n)
    right := make([]int, n)
    for i := range left {
        left[i], right[i] = 1, 1
    }

    for i := 1; i < n; i++ {
        if nums[i] >= nums[i-1] {
            left[i] = left[i-1] + 1
        }
    }

    for i := n - 2; i >= 0; i-- {
        if nums[i] <= nums[i+1] {
            right[i] = right[i+1] + 1
        }
    }

    ans := slices.Max(left)

    for i := 0; i < n; i++ {
        a := 0
        if i > 0 {
            a = left[i-1]
        }
        b := 0
        if i+1 < n {
            b = right[i+1]
        }
        if i > 0 && i+1 < n && nums[i-1] > nums[i+1] {
            ans = max(ans, max(a+1, b+1))
        } else {
            ans = max(ans, a+b+1)
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function longestSubarray(nums: number[]): number {
    const n = nums.length;
    const left: number[] = Array(n).fill(1);
    const right: number[] = Array(n).fill(1);

    for (let i = 1; i < n; i++) {
        if (nums[i] >= nums[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }

    for (let i = n - 2; i >= 0; i--) {
        if (nums[i] <= nums[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
    }

    let ans = Math.max(...left);

    for (let i = 0; i < n; i++) {
        const a = i - 1 < 0 ? 0 : left[i - 1];
        const b = i + 1 >= n ? 0 : right[i + 1];
        if (i - 1 >= 0 && i + 1 < n && nums[i - 1] > nums[i + 1]) {
            ans = Math.max(ans, Math.max(a + 1, b + 1));
        } else {
            ans = Math.max(ans, a + b + 1);
        }
    }

    return ans;
}

Comments