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;
    }
};
共 0 条回复
暂时没有人回复哦,赶紧抢沙发
发表新回复

作者

sryan
today is a good day