【LeetCode】665. 非递减数列

发表于 更新于 分类于 Valine：
本文字数： 93 阅读时长 ≈ 1 分钟

665. 非递减数列

思路

错误代码

输入 [3,4,2,3]
输出 false

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int c=0;
        for(int i=0;i<nums.size()-1;i++)
        {
            if(nums[i]>nums[i+1])   c++;
            if(c>1) return false;
        }
        return true;
    }
};

拓展

  1. is_sorted()：判断函数是否被排序好，默认升序，C++11特性
  2. sort()：将函数进行排序处理，默认升序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//优化后只遍历一次nums数组
class Solution {
public:
    bool checkPossibility(vector<int> &nums) {
        int n = nums.size(), cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                cnt++;
                if (cnt > 1) {
                    return false;
                }
                if (i > 0 && y < nums[i - 1]) {
                    nums[i + 1] = x;
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//未优化，多次遍历nums数组
class Solution {
public:
    bool checkPossibility(vector<int> &nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                nums[i] = y;
                if (is_sorted(nums.begin(), nums.end())) {
                    return true;
                }
                nums[i] = x; // 复原
                nums[i + 1] = x;
                return is_sorted(nums.begin(), nums.end());
            }
        }
        return true;
    }
};