你最多只可遴选其中一个位置的元素，把它改成狂放整数（也不错遴选不改）。

在允许这种“最多一次蜕变”的情况下，求能得到的最长说合非递减子数组的长度。

所谓“非递减子数组”，指的是该说合片断中狂放相邻两项齐喜跃：后一个元素 不小于 前一个元素。

子数组示意数组中一段说合的元素序列。

1

-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完整代码如下：

package main

import (

"fmt"

)

func longestSubarray(nums []int)int {

pre0， f0， f1 := 0， 1， 1

ans := 1// 以 nums[0] 遣散的子数组长度

for i := 1; i

tmp := f0

if nums[i-1]

f0++

f1++

} else {

f0 = 1

f1 = 0// 破除旧数据

}

if i >= 2 && nums[i-2]

f1 = max(f1， pre0+2)

} else {

f1 = max(f1， 2)

}

ans = max(ans， tmp+1， f1)

pre0 = tmp

}

return ans

}

func main {

nums := []int{1， 2， 3， 1， 2}

result := longestSubarray(nums)

fmt.Println(result)

}

Python完整代码如下：

# -*-coding:utf-8-*-

def longestSubarray(nums):

if not nums:

return0

pre0， f0， f1 = 0， 1， 1

ans = 1 # 以 nums[0] 遣散的子数组长度

for i in range(1， len(nums)):

tmp = f0

if nums[i-1]

f0 += 1

f1 += 1

else:

f0 = 1

f1 = 0 # 破除旧数据

if i >= 2 and nums[i-2]

f1 = max(f1， pre0 + 2)

else:

f1 = max(f1， 2)

ans = max(ans， tmp + 1， f1)

pre0 = tmp

return ans

def main:

nums = [1， 2， 3， 1， 2]

result = longestSubarray(nums)

print(result)

if __name__ == "__main__":

main

C++完整代码如下：

#include

#include

#include

using namespace std;

int longestSubarray(vector& nums) {

if (nums.empty) return0;

int pre0 = 0， f0 = 1， f1 = 1;

int ans = 1; // 以 nums[0] 遣散的子数组长度

for (int i = 1; i

int tmp = f0;

if (nums[i-1]

f0++;

f1++;

} else {

f0 = 1;

f1 = 0; // 破除旧数据

}

if (i >= 2 && nums[i-2]

f1 = max(f1， pre0 + 2);

} else {

f1 = max(f1， 2);

}

ans = max({ans， tmp + 1， f1});

pre0 = tmp;

}

return ans;

}

int main {

vector nums = {1， 2， 3， 1， 2};

int result = longestSubarray(nums);

cout

return0;

}

咱们信服东谈主工智能为平淡东谈主提供了一种“增强器具”，并尽力于共享全标的的AI学问。在这里，您不错找到最新的AI科普著述、器具评测、教学规章的心事以及行业知悉。

宽待温雅“福大大架构师逐日一题”银河国际游戏平台官网，发音尘可取得口试辛勤，让AI助力您的异日发展。

开云体育官方网站 - KAIYUN

• 一个
• 银河国际游戏平台官网
• 至多
• 替换
• 2026-03-27