0665. 非递减数列 #
- 标签:数组
- 难度:简单
题目大意 #
给定一个整数数组 nums,问能否在最多改变 1 个元素的条件下,使数组变为非递减序列。若能,返回 True,不能则返回 False。
解题思路 #
循环遍历数组,寻找 nums[i] > nums[i+1] 的情况,一旦这种情况出现超过 2 次,则不可能最多改变 1 个元素,直接返回 False。
遇到 nums[i] > nums[i+1] 的情况,应该手动调节某位置上元素使数组有序。此时,有两种选择:
- 将 nums[i] 调低,与 nums[i-1] 持平
- 将 nums[i+1] 调高,与 nums[i] 持平
若选择第一种调节方式,如果调节前 nums[i-1] > nums[i+1],那么调节完 nums[i] 之后,nums[i-1] 还是比 nums[i+1] 大,不可取。
所以应选择第二种调节方式,如果调节前 nums[i-1] > nums[i+1],那么调节完 nums[i+1] 之后 nums[i-1] < nums[i] <= nums[i+1],满足非递减要求。
最终如果最多调整过一次,且 nums[i] > nums[i+1] 的情况也最多出现过一次,则返回 True。
代码 #
|
|