Non-decreasing Array

Posted by chunyang on April 5, 2019

题目

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3]

Output: True

Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]

Output: False

Explanation: You can’t get a non-decreasing array by modify at most one element. Note: The n belongs to [1, 10,000].

解法

算法复杂度 O(n),空间复杂度 O(1)

思路

这个数组除了一个元素外,其它元素都是有序的,如果我们摘除这个元素,那么摘除后的数组是有序的。怎么找 到这个摘除的元素呢?如果我们遇到了第一个 nums[i] > nums[i+1] 的元素。说明这个位置附近必须要调整, 而且这种调整只能出现一次,因为题目要求最多只能修改一次。

a = nums[i-1]

b = nums[i]

c = nums[i+1]

d = nums[i+2]

这 4 个值必须满足一定关系我们才能调整它为有序,关系是:

  • a <= d
  • b>=a && b <=d or `c>=a && c<=d

找到这种逆序对后,它将数组拆成两个各自有序的数组,且两个数组块要满足前者最大值小于等于后者最小者。 二者这个逆序对这两个元素也必须在这个最大值和最小值之间。

代码

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int start = 0;
        int end = nums.size();
        int reversal = 0;
        int a, b, c, d;
        a = INT_MIN;
        d = INT_MAX;
        while (start < end - 1) {
            if (nums[start] > nums[start+1]) {
                if (reversal != 0) {
                    return false;
                }
                reversal += 1;
                b = nums[start];
                c = nums[start+1];
                if (start > 0) a = nums[start - 1];
                if (start + 2 < end) d = nums[start+2];
                bool bb = b >= a && b <= d;
                bool cc = c >= a && c <= d;
                if (!(bb || cc)) {
                    return false;
                }

            }
            ++start;
        }
        return true;
        // cout << a << " " << b << " " << c <<  " " << d << endl;
    }
};

本文完


Creative Commons License
This work is licensed under a CC A-S 4.0 International License.