跳转至

LeetCode: 665. 非递减数列

1、题目描述

给定一个长度为 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]。

2、解题思路

  • 设置两个指针,左面和右面的指向了左面第一个减小的位置,右面指向了右面第一个减小的位置
  • 判断这两个中间,有几次递减机会,超过一次,返回false
  • 如果只有一次,找出中间的最大值,最小值
  • 最小值和左面的值进行比较,如果小于,并且最大值和右面的一个值比较,如果大于,这种情况是不可以的,返回false
  • 其他的都是true
bool checkPossibility(int* nums, int numsSize) {


    int left_pos = 0;
    int right_pos = numsSize - 1;

    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i + 1] < nums[i]) {
            left_pos = i;
            break;
        }
    }
    if (left_pos == numsSize - 1) {
        return true;
    }

    for (int i = numsSize - 1; i > 0; i--) {
        if (nums[i - 1] > nums[i]) {
            right_pos = i;
            break;
        }
    }


    // 找到区间的最大最小值
    int max = INT32_MIN;
    int min = INT32_MAX;
    int count = 0;
    for (int i = left_pos; i <= right_pos; i++) {
        if (nums[i] > max) {
            max = nums[i];
        }

        if (nums[i] < min) {
            min = nums[i];
        }

        if (i + 1 <= right_pos && nums[i + 1] < nums[i]) {
            count++;
        }

    }
    if (count >= 2) {
        return false;
    }

    if (left_pos > 0 && right_pos < numsSize - 1) {
        if (max > nums[right_pos + 1] && min < nums[left_pos - 1]) {
            return false;
        }
    }

    return true;


}