

LeetCode: 665. 非递减数列

• LeetCode: 665. 非递减数列
  • 1、题目描述
  • 2、解题思路

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;


}