Non-decreasing Array (Easy Google)

update May 13,2018 0:22

LeetCode

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].

Basic Idea:

这道题的重点是判断什么样的局部断点是可以通过改变一个元素来恢复有序性的。只有两种可能，要么断点处比两端都高，要么断点处比两端都低。第一种情况，当我们出现 nums[i] > nums[i + 1] 时，如果 nums[i-1]<=nums[i+1]，则说明断点处 i 比两边都高。第二种，如果 nums[i]<=nums[i+2]，则说明断点处 i+1 比两端都低。另外注意处理极左和极右的情况。除了这些情况之外，遇到断点可以直接返回false，否则当遇到超过一次断点时返回false。

另外一个方法是当遇到 nums[i] > nums[i+1] 时，分别判断去掉 i 和去掉 i+1 后原数组是否是不降低序列，这种方法比较好理解，只要另外写一个helper function 判断是否不降低序列就好。

• C++ Code:

    class Solution {
    public:
        bool checkPossibility(vector<int>& nums) {
            if (nums.empty() || nums.size() < 3) return true;
            int encountered = false;
            for (int i = 0; i < nums.size() - 1; ++i) {
                if (nums[i] > nums[i + 1]) {
                    if (i == 0 || i == nums.size() - 2 || nums[i] <= nums[i + 2] || nums[i - 1] <= nums[i + 1]) {
                        if (encountered) return false;
                        else encountered = true;
                    } else {
                        return false;
                    }
                }
            }
            return true;
        }
    };

•   class Solution {
        public boolean checkPossibility(int[] nums) {
            boolean breaked = false;
            for (int i = 0; i < nums.length - 1; ++i) {
                if (nums[i] > nums[i + 1]) {
                    if (i == 0 || i == nums.length - 2 || nums[i + 2] >= nums[i] || nums[i - 1] <= nums[i + 1]) {
                        if (breaked) return false;
                        else breaked = true;
                    } else {
                        return false;
                    }
                }
            }
            return true;
        }
    }