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

这道题submit了2次，第一次想简单了，然后就wrong了。其实看完上面两个例子，就想简单了，提交的时候看着提交的通过率16.9K/134.2K就觉得这道题不简单，于是果真提交后，这种case下倒下了 3,4,2,3。

一开始想，只要遍历这个数组，然后统计前一个比后一个大的次数就行了，大于1直接返回错误。可是submit失败后，才发现不是这样的。后来想了一种办法来解决，当然我这种办法在提交accept之后看了solution，没有发现一样的方法，所以我就在这里记录下来了，不少人也提到这道题不应该归为easy，应该为medium。

解题的大概思路为，依旧和一开始的思路一致，依旧扫描nums[i-1]与当前的nums[i]，假如后面大于等于前面的，那肯定pass，假设小于了，那么肯定要记一次数，因为肯定要进行替换，但是在替换之后，后续的nums的比较不能和前面的元素进行比较了，必须和之前最大的元素进行比较。替换这里有两种情况：

1. 将nums[i-1]替换为nums[i]。这种情况下，即将大的元素替换为后面的元素来保证替换后整个数组处于non decreasing状态。满足这种替换条件有两种，一种是nums[i-1]为第一个元素，直接可以替换，第二种是nums[i-2]小于等于nums[i]，这样nums[i-1]替换为nums[i]之后，不会导致数组降序。在替换之后，整个数组的最大值就变为了nums[i]了。以后nums[i]必须和这个值进行比较来确定是否数组递减了。

2. 将nums[i]替换为nums[i-1]。在不满足该条件1的情况下，做这步操作，该操作不会影响前面已遍历数组的最大值。

3. 直至扫描至尾元素，若计数一直小于等于1，则返回true，否则false

可以看到，最主要的一点是，nums[i]需要和谁进行比较，应该是和前面一个子串的最大值进行比较，而最优的解就是将nums[i-1]进行替换，替换为nums[i]，这样可以将整个子串的最大值减小，后续更容易满足非递减的条件。

下面贴一下我的解法：

class NonDecreasingArray {
public:
    static void test() {
        vector<int> nums;
        nums.push_back(4);
        nums.push_back(2);
        nums.push_back(3);
        auto ret = main(nums);
    }

    static bool main(vector<int>& nums) {
        if (nums.size() <= 1) {
            return true;
        }
        int cnt = 0;
        int premax = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (premax > nums[i]) {
                ++cnt;
                if (cnt > 1) {
                    return false;
                }
                if (i - 1 == 0 || nums[i - 2] <= nums[i]) {
                    if (premax == nums[i - 1]) {
                        premax = nums[i];
                    }
                }
            } else {
                premax = nums[i];
            }
        }
        return true;
    }
};