2026-03-27：替换至多一个元素后最长非递减子数组。用go语言，给定一个整数数组 nums。 你最多只能选择其中一个位置的元素，把它改成任意整数（也可以选择不改）。 在允许这种“最多一次改动”的

2026-03-27：替换至多一个元素后最长非递减子数组。用go语言，给定一个整数数组 nums。

你最多只能选择其中一个位置的元素，把它改成任意整数（也可以选择不改）。

在允许这种“最多一次改动”的情况下，求能得到的最长连续非递减子数组的长度。

所谓“非递减子数组”，指的是该连续片段中任意相邻两项都满足：后一个元素 不小于 前一个元素。

子数组表示数组中一段连续的元素序列。

1 <= nums.length <= 100000。

-1000000000 <= nums[i] <= 1000000000。

输入: nums = [1,2,3,1,2]。

输出: 4。

解释:

将 nums[3] = 1 替换为 3 得到数组 [1, 2, 3, 3, 2]。

最长非递减子数组是 [1, 2, 3, 3]，其长度为 4。

题目来自力扣3738。

一、题目核心理解

我们的目标是：最多修改数组中1个元素（也可以不修改），找到数组中最长的连续非递减子数组（连续片段，相邻元素后≥前）。
示例：[1,2,3,1,2]，修改第4个元素1为3，得到[1,2,3,3,2]，最长子数组长度为4。

二、核心思路：动态规划（状态记录）

这道题用动态规划解决，核心是遍历数组时，记录两个关键状态，不额外存储全量数据，仅用变量更新：

1. 状态1（f0）：以当前元素结尾，不修改任何元素的最长非递减子数组长度；
2. 状态2（f1）：以当前元素结尾，已经修改过1个元素的最长非递减子数组长度；
3. 额外用变量记录历史状态，辅助计算修改操作后的长度。

遍历数组时，每一步都根据前一个元素和当前元素的大小关系，更新这两个状态，并同步记录全局最大值。

三、分步骤详细执行过程（以 nums = [1,2,3,1,2] 为例）

数组索引：0:1, 1:2, 2:3, 3:1, 4:2
初始状态：

• pre0：保存上上个位置的f0值（初始0）
• f0：当前不修改的最长长度（初始1，第一个元素自身）
• f1：当前修改1次的最长长度（初始1）
• ans：最终答案（初始1）

步骤1：遍历索引 i=1（元素=2）

前一个元素是索引0（1），满足1 ≤ 2（非递减）：

1. 不修改的长度f0：在前一个f0基础上+1 → 变为2；
2. 修改1次的长度f1：在前一个f1基础上+1 → 变为2；
3. 检查是否能通过修改元素延长子数组：满足条件，更新f1；
4. 全局最大值ans更新为2。

步骤2：遍历索引 i=2（元素=3）

前一个元素是索引1（2），满足2 ≤ 3：

1. 不修改的长度f0：+1 → 变为3；
2. 修改1次的长度f1：+1 → 变为3；
3. 检查修改逻辑，更新f1；
4. 全局最大值ans更新为3。

步骤3：遍历索引 i=3（元素=1）【关键修改点】

前一个元素是索引2（3），不满足3 ≤ 1（递减）：

1. 不修改的长度f0：无法延续，重置为1（仅自身）；
2. 核心：这里可以执行一次修改操作，把当前元素1改成≥3的数（比如3）；
3. 修改1次的长度f1：结合前两段有效长度，计算得到4；
4. 全局最大值ans更新为4（这就是示例的答案）。

步骤4：遍历索引 i=4（元素=2）

前一个元素是索引3（1），满足1 ≤ 2：

1. 不修改的长度f0：+1 → 变为2；
2. 修改1次的长度f1：延续之前的状态+1；
3. 全局最大值ans保持4不变。

最终结果

遍历结束，全局最大值为4，与题目输出一致。

四、核心逻辑总结

1. 连续非递减时：不修改和修改过的长度都直接+1，延续子数组；
2. 出现递减时：
   • 不修改的长度直接重置为1（无法连续）；
   • 利用唯一一次修改机会，把当前递减的元素改成合适值，拼接前后两段有效子数组，计算修改后的最长长度；
3. 全程只更新几个变量，不存储多余数据，实时更新最长长度。

五、复杂度分析

1. 时间复杂度

• 我们只遍历了数组一次，每个元素仅做常数次计算（判断、加减、取最大值）；
• 时间复杂度：O(n)（n为数组长度）。
• 适配题目要求：n最大10万，O(n)是最优效率，无超时风险。

2. 额外空间复杂度

• 全程仅使用了固定数量的变量（pre0、f0、f1、ans、临时变量）；
• 没有创建数组、哈希表等与n相关的额外数据结构；
• 额外空间复杂度：O(1)（常数级空间）。

总结

1. 解题核心：动态规划+双状态（不修改/修改1次），遍历一次数组完成计算；
2. 执行过程：遇到非递减直接延长，遇到递减用唯一修改机会拼接子数组；
3. 效率：时间O(n)，空间O(1)，完美适配大数据量的题目要求。

Go完整代码如下：

packagemainimport("fmt")funclongestSubarray(nums[]int)int{pre0,f0,f1:=0,1,1ans:=1// 以 nums[0] 结尾的子数组长度fori:=1;i<len(nums);i++{tmp:=f0ifnums[i-1]<=nums[i]{f0++f1++}else{f0=1f1=0// 清除旧数据}ifi>=2&&nums[i-2]<=nums[i]{f1=max(f1,pre0+2)}else{f1=max(f1,2)}ans=max(ans,tmp+1,f1)pre0=tmp}returnans}funcmain(){nums:=[]int{1,2,3,1,2}result:=longestSubarray(nums)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-deflongestSubarray(nums):ifnotnums:return0pre0,f0,f1=0,1,1ans=1# 以 nums[0] 结尾的子数组长度foriinrange(1,len(nums)):tmp=f0ifnums[i-1]<=nums[i]:f0+=1f1+=1else:f0=1f1=0# 清除旧数据ifi>=2andnums[i-2]<=nums[i]:f1=max(f1,pre0+2)else:f1=max(f1,2)ans=max(ans,tmp+1,f1)pre0=tmpreturnansdefmain():nums=[1,2,3,1,2]result=longestSubarray(nums)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intlongestSubarray(vector<int>&nums){if(nums.empty())return0;intpre0=0,f0=1,f1=1;intans=1;// 以 nums[0] 结尾的子数组长度for(inti=1;i<nums.size();i++){inttmp=f0;if(nums[i-1]<=nums[i]){f0++;f1++;}else{f0=1;f1=0;// 清除旧数据}if(i>=2&&nums[i-2]<=nums[i]){f1=max(f1,pre0+2);}else{f1=max(f1,2);}ans=max({ans,tmp+1,f1});pre0=tmp;}returnans;}intmain(){vector<int>nums={1,2,3,1,2};intresult=longestSubarray(nums);cout<<result<<endl;return0;}