leetcode分类刷题之“数组”分类—— 非递减数列(# 665)

题目描述

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

示例 1:

输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
说明: n 的范围为 [1, 10,000]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/non-decreasing-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

开始思路是打算，替换一次，判断一次是否有序，如果替换了一次，仍然不满足“非递减”，则false，或者一直替换序列到有序，计算替换的次数，如果替换的次数大于1，则false。
但是自己写出来的代码一直过不去。尴尬

先放上题解区里一位大佬的答案

 def isSort(arr):for i in range(len(arr) - 1):if arr[i] > arr[i + 1]:return Falsereturn Truefor i in range(len(nums) - 1):if nums[i] > nums[i + 1]:# i, i + 1中的两个元素, 肯定有一个被替换掉# 替换掉的情况下, 原数组保持有序, 则为有序t1 = isSort(nums[0:i] + nums[i + 1:])t2 = isSort(nums[0:i + 1] + nums[i + 2:])return t1 or t2return True作者：leicj
链接：https://leetcode-cn.com/problems/non-decreasing-array/solution/python3-fei-di-jian-shu-lie-by-leicj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

官方题解：

方法一

很遗憾，这个方法多次尝试没有做出来，我有些怀疑这个方法的正确性，，，，
[-1,4,2,3]，这个样例中，并不能如题解中的方法“将A[i] 更改为A[i-1]”解决。

上面的评论区大佬，则合并了“将A[i] 更改为A[i-1]”和“将A[i-1] 更改为A[i]”的情况，并且，巧妙地变“替换”为“删除”，避免了$O(N)$的空间复杂度。时间复杂度仍然为 O ( N 2 ) O(N^2) O(N2)

好吧，下面的解法我暂时看不懂。

方法二

作者：LeetCode
链接：https://leetcode-cn.com/problems/non-decreasing-array/solution/fei-di-jian-shu-lie-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

很遗憾一天刷一题愿望是美好的。毕竟自己太菜，，，

本题在B的一个up主讲解。传送门

看了这个up主的视频，才知道刚开始为什么我的方法不对，我只是单纯考虑了计数，超过1的返回false；没有考虑到有两种替换情况。
看了up主的视频后，写代码如下：

class Solution:def checkPossibility(self, nums: List[int]) -> bool:count = 0for i in range(1, len(nums)):if (nums[i] < nums[i - 1]):count += 1if (count > 1):return Falseif (i - 2 < 0 or nums[i - 2] <= nums[i]):nums[i - 1] = nums[i]else:nums[i] = nums[i - 1]return True

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！