非递减数列

发表于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

LeetCode每日一题，665. Non-decreasing Array

先看题目描述

ytRDSA.png

大意就是给定一个数组 nums，让我们判断，能否改变 nums 中至多一个数字，使其为非递减数列

算法和思路

算法流程

  • 遍历数组找到第一个元素 nums[i] 满足 nums[i] > nums[i + 1]，若找不到的话，则说明 nums 已经是非递减数列，直接返回 true
  • 此时有 nums[0: i] 为非递减数列，nums[i] > nums[i + 1]，再对数组 nums[i + 2: len - 1] 部分进行判断，若该部分不是非递减的，则直接返回 false，不可能改变至多一个数字使 nums 为非递减数列
  • 若 nums[i + 2: len - 1] 部分也是非递减数列，那么再进行考虑，考虑两种情况，此时 nums[0: i] 为非递减数列，nums[i + 2: len - 1] 也是非递减数列，nums[i] > nums[i + 1]，想让 nums 是非递减数列，可以考虑改变 nums[i] 或 nums[i + 1]
    • 若 nums[i] <= nums[i + 2]，则该情况下是 nums[i + 1] 小了，改变 nums[i + 1] 即可让 nums 为非递减数列，返回 true 即可
    • 若 nums[i - 1] <= nums[i + 1] 且 nums[i + 1] <= nums[i + 2]，则该情况下是 nums[i] 大了，改变 nums[i] 即可让 nums 为非递减数列即可，返回 true 即可
    • 若不满足上述两种情况中的任意一种，则不能改变至多一个数字使 nums 为非递减数列，返回 false

算法源码

注意：实现代码时要考虑 i 为 0 或 i 为 len - 2 的特殊情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean checkPossibility(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            if (nums[i] <= nums[i + 1]) {
                continue;
            }
            if (i == len - 2) {
                return true;
            }
            for (int j = i + 2; j < len - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    return false;
                }
            }
            if (i == 0 && nums[1] <= nums[2]) {
                return true;
            } else if (nums[i] <= nums[i + 2]) {
                return true;
            } else if (nums[i + 1] <= nums[i + 2] && nums[i - 1] <= nums[i + 1]) {
                return true;
            } else {
                return false;
            }
        }
        return true;
    }
}