Non-decreasing Array

题目
解法
- 思路
- 代码

题目

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;
    }
};

本文完