0665. Non-decreasing Array

题目信息

题号:

0665

难度:

Medium

主题:

数组、非递减顺序、至多一次修改、可行性判断

原题:

LeetCode 0665

重点:

可以把至多一个位置改成任意整数、修改后所有相邻项都需满足前项不大于后项、不要求返回修改方案

题目重述

给定整数数组 nums,判断能否通过修改至多一个数组元素,使整个数组成为非递减数组。

一次修改可以把选定位置替换为任意整数;也可以不修改任何元素。非递减要求对每个有效下标 i 都满足 nums[i] <= nums[i+1],相等是允许的。nums.length 位于 [1, 10^4],元素值位于 [-10^5, 10^5]。

自建示例

一次修改可以修复两个相邻关系:

输入:nums = [2,5,3,4]
输出:true
解释:把 5 改为 3,可得到 [2,3,3,4],整个数组非递减。

至少需要修改两个位置:

输入:nums = [4,2,3,1]
输出:false
解释:前部的 4>2 与末尾的 3>1 无法通过修改同一个位置同时消除,因此一次修改不足。