Leetcode 665 非递减数列

本文主要是介绍Leetcode 665 非递减数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述

  给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
  我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

二、示例及约束

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

示例 2：
输入： nums = [4,2,1]
输出： false
解释： 你不能在只改变一个元素的情况下将其变为非递减数列。

示例 3：
输入： nums = [1]
输出： true

示例 4：
输入： nums = [3,1]
输出： true

示例 5：
输入： nums = [3,4,2,3]
输出： false

提示：
● n == nums.length
● 1 <= n <= $10^4$
● $-10^5$ <= nums[i] <= $10^5$

三、代码

方法一：直接判断

class Solution {
public:bool checkPossibility(vector<int>& nums) {int count = 0, n = nums.size();//如果n小于3时，一定能成为非递减数列if (n <= 2) {return true;}for (int i = 0; i < n - 1; i++) {//如果发现相邻递减，count计数加1if (nums[i] > nums[i + 1]) {count++;//count大于1时，修改一个不够成为非递减数列if (count > 1) {return false;} /*count小于等于1时，不一定就是非递减数列，如自用示例5中的样例[3，4，2，3]。对于这个样例来说，想让他变成非递减数列，那么在第一次发现递减情况时有两种情况，将2变成4，或将4变成3这两种方式，但是这两种方式都行不通，说明它不能修改成非递减数列。即应在第一次发现递减情况（此时称之为数1和数2）时设立两个额外的判断标准：数1应该小于等于往后隔一位的数，或数2应该大于等于往前隔一位的数。若这两个标准都不通过，说明不能修改成非递减数列。*/if (i >= 1 && i <= n - 3) {//注意下标if (nums[i + 2] < nums[i] && nums[i - 1] > nums[i + 1] ) {return false;}}}}//false情况全部判断完，其余则是true情况return true;}
};

方法二：修改后判断

class Solution {
public:bool checkPossibility(vector<int> &nums) {int n = nums.size(), cnt = 0;for (int i = 0; i < n - 1; ++i) {//用x来记录当前遍历到的数，y来记录x的后一位数int x = nums[i], y = nums[i + 1];if (x > y) {//递减情况cnt加1cnt++;//cnt大于1则表示不能修改成非递减数列if (cnt > 1) {return false;}//如果发现x的后一位比x的前一位还小，那么将x的后一位修改成x，如果修改之后cnt还是大于1，说明修改1次不够使其成为非递减数列if (i > 0 && y < nums[i - 1]) {nums[i + 1] = x;}}}return true;//return is_sorted(nums.begin(), nums.end());/*这里学习到了is_sorted方法，is_sorted函数是C++标准库中的一个算法，用于判断一个序列是否已经按照指定的排序准则排序好了,复杂度与数组长度有关。它接受两个迭代器参数，指定序列的范围，并返回一个布尔值来指示序列是否已按照升序排列。如果序列已经排序好了，则返回true；否则返回false。*/}
};

四、总结

时间复杂度：
方法一：O(n)，其中 n 是数组 nums 的长度。
方法二：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：
方法一：O(1)。
方法二：O(1)。

方法	时间复杂度	空间复杂度
方法一	O($n$)	O(1)
方法二	O($n$)	O(1)

这篇关于Leetcode 665 非递减数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---