Medium

题目描述

给你一个整数数组 nums。

你可以将数组中至多一个元素替换为你选择的任何其他整数值。

返回执行至多一次替换后可以获得的最长非递减子数组的长度。

如果一个数组的每个元素都大于或等于其前一个元素（如果存在的话），则称该数组为非递减的。

示例 1：

输入：nums = [1,2,3,1,2]
输出：4
解释：
将 nums[3] = 1 替换为 3，得到数组 [1, 2, 3, 3, 2]。
最长非递减子数组是 [1, 2, 3, 3]，长度为 4。

示例 2：

输入：nums = [2,2,2,2,2]
输出：5
解释：
nums 中的所有元素都相等，所以它已经是非递减的，整个 nums 形成长度为 5 的子数组。

约束条件：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

这道题可以使用前缀和后缀数组的方法来解决。核心思路是：对于每个位置，考虑将该位置替换后能够获得的最长非递减子数组。

解题思路：

  1. 预处理前缀数组：pref[i] 表示以位置 i 结尾的最长非递减子数组长度
  2. 预处理后缀数组：suff[i] 表示从位置 i 开始的最长非递减子数组长度
  3. 考虑三种情况：
    • 不进行替换：答案为 max(pref) 或 max(suff)
    • 替换位置 i：尝试连接 pref[i-1] 和 suff[i+1]
    • 替换后只考虑单侧：pref[i-1] + 1 或 suff[i+1] + 1

关键点：

  • 连接前后缀时需要检查 nums[i-1] <= nums[i+1]，确保替换后仍然非递减
  • 边界处理：考虑替换首尾元素的情况
  • 时间复杂度为 O(n)，空间复杂度为 O(n)

这种方法通过预处理避免了重复计算，能够高效地找到最优解。

代码实现

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 1;
        
        // 前缀数组：pref[i] 表示以 i 结尾的最长非递减子数组长度
        vector<int> pref(n, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] >= nums[i-1]) {
                pref[i] = pref[i-1] + 1;
            }
        }
        
        // 后缀数组：suff[i] 表示从 i 开始的最长非递减子数组长度
        vector<int> suff(n, 1);
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= nums[i+1]) {
                suff[i] = suff[i+1] + 1;
            }
        }
        
        // 不替换的情况下的最大长度
        int maxLen = *max_element(pref.begin(), pref.end());
        
        // 尝试替换每个位置
        for (int i = 0; i < n; i++) {
            // 替换位置 i 后的可能长度
            int len = 1;
            
            // 连接左侧和右侧
            if (i > 0 && i < n-1 && nums[i-1] <= nums[i+1]) {
                len = pref[i-1] + suff[i+1];
            }
            // 只考虑左侧
            else if (i > 0) {
                len = pref[i-1] + 1;
            }
            // 只考虑右侧
            else if (i < n-1) {
                len = suff[i+1] + 1;
            }
            
            maxLen = max(maxLen, len);
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 1
        
        # 前缀数组：pref[i] 表示以 i 结尾的最长非递减子数组长度
        pref = [1] * n
        for i in range(1, n):
            if nums[i] >= nums[i-1]:
                pref[i] = pref[i-1] + 1
        
        # 后缀数组：suff[i] 表示从 i 开始的最长非递减子数组长度
        suff = [1] * n
        for i in range(n-2, -1, -1):
            if nums[i] <= nums[i+1]:
                suff[i] = suff[i+1] + 1
        
        # 不替换的情况下的最大长度
        max_len = max(pref)
        
        # 尝试替换每个位置
        for i in range(n):
            # 替换位置 i 后的可能长度
            length = 1
            
            # 连接左侧和右侧
            if i > 0 and i < n-1 and nums[i-1] <= nums[i+1]:
                length = pref[i-1] + suff[i+1]
            # 只考虑左侧
            elif i > 0:
                length = pref[i-1] + 1
            # 只考虑右侧
            elif i < n-1:
                length = suff[i+1] + 1
            
            max_len = max(max_len, length)
        
        return max_len

public class Solution {
    public int LongestSubarray(int[] nums) {
        int n = nums.Length;
        if (n == 1) return 1;
        
        // 前缀数组：pref[i] 表示以 i 结尾的最长非递减子数组长度
        int[] pref = new int[n];
        Array.Fill(pref, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] >= nums[i-1]) {
                pref[i] = pref[i-1] + 1;
            }
        }
        
        // 后缀数组：suff[i] 表示从 i 开始的最长非递减子数组长度
        int[] suff = new int[n];
        Array.Fill(suff, 1);
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= nums[i+1]) {
                suff[i] = suff[i+1] + 1;
            }
        }
        
        // 不替换的情况下的最大长度
        int maxLen = pref.Max();
        
        // 尝试替换每个位置
        for (int i = 0; i < n; i++) {
            // 替换位置 i 后的可能长度
            int len = 1;
            
            // 连接左侧和右侧
            if (i > 0 && i < n-1 && nums[i-1] <= nums[i+1]) {
                len = pref[i-1] + suff[i+1];
            }
            // 只考虑左侧
            else if (i > 0) {
                len = pref[i-1] + 1;
            }
            // 只考虑右侧
            else if (i < n-1) {
                len = suff[i+1] + 1;
            }
            
            maxLen = Math.Max(maxLen, len);
        }
        
        return maxLen;
    }
}

var longestSubarray = function(nums) {
    const n = nums.length;
    if (n <= 1) return n;
    
    let maxLen = 1;
    
    // For each position i, try replacing nums[i]
    for (let i = 0; i < n; i++) {
        // Find longest non-decreasing subarray ending at i-1
        let left = i;
        while (left > 0 && nums[left - 1] <= nums[left]) {
            left--;
        }
        
        // Find longest non-decreasing subarray starting at i+1
        let right = i;
        while (right < n - 1 && nums[right] <= nums[right + 1]) {
            right++;
        }
        
        // Case 1: Don't replace, just take the existing subarray
        maxLen = Math.max(maxLen, right - left + 1);
        
        // Case 2: Replace nums[i] and try to connect left and right parts
        if (left < i && right > i) {
            // Can we connect by replacing nums[i]?
            if (nums[left] <= nums[right]) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }
        
        // Case 3: Replace nums[i] and extend left part
        if (left < i) {
            let extendRight = i;
            while (extendRight < n - 1 && nums[i - 1] <= nums[extendRight + 1]) {
                extendRight++;
            }
            maxLen = Math.max(maxLen, extendRight - left + 1);
        }
        
        // Case 4: Replace nums[i] and extend right part  
        if (right > i) {
            let extendLeft = i;
            while (extendLeft > 0 && nums[extendLeft - 1] <= nums[i + 1]) {
                extendLeft--;
            }
            maxLen = Math.max(maxLen, right - extendLeft + 1);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要三次遍历数组：构建前缀数组、构建后缀数组、尝试替换每个位置
空间复杂度O(n)需要额外的前缀和后缀数组存储空间