NonDecreasingArray [source code]

public class NonDecreasingArray {
static
/******************************************************************************/
class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++)
            if (!(nums[i] <= nums[i + 1])) {
                if (count > 0)
                    return false;
                if (i - 1 >= 0 && i + 2 < nums.length && (nums[i] > nums[i + 2] && nums[i + 1] < nums[i - 1]))
                    return false;
                count++;
            }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        NonDecreasingArray.Solution tester = new NonDecreasingArray.Solution();
        int[][] inputs = {
            {3,4,2,3}, {0},
            {2,3,3,2,4}, {1},
            {1,3,5,2,4}, {0},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            boolean ans = inputs[1 + 2 * i][0] == 1;
            System.out.println(Printer.separator());
            boolean output = tester.checkPossibility(nums);
            System.out.println(
                Printer.wrapColor(Printer.array(nums), "magenta") +
                " -> " + output +
                Printer.wrapColor(", expected: " + ans, ans == output ? "green" : "red")
                );
        }
    }
}

还是从笨办法开始做; 刚开始写了一个很trivial的做法, 就是数一下downtick的个数, 只要不超过1就是true; 但是这个思路立刻被inputs的第一个给break了; 当然, 这个错误的思路还是有帮助的;

Google的题目还是那个特点, 你想的多美的算法最后人家都能找一个corner case给你break掉; 这个题目大体的思路其实很早就有了, 关键是怎么调整; 不过这个题目本身还是很有意思的: 看上去是一个很trivial的题目, 但是最后OJ引导你一步一步的走向对题目的正确的intuition;

刚开始的想法是, 只要不超过一个downtick就行了, 但是这个不对; 然后思考, 这里的modify是什么意思, 然后怀疑, 只要downtick的左右两边的两个数字维持nondecreasing就行了, 但是这个其实也不对; 最后才发现, downtick两边的两个邻居形成的这个范围是一个关键; 要保证只要modify一个element就能进入全体non-decreasing, 必须保证修改一个downtick的两个端点当中的一个之后, 两个端点都能够维持在这两个邻居围成的这个range当中; 所以只要保证downtick的两个端点不同时超界就行了;

最后的速度是30ms (N/A), 这个题目总体还是挺好玩的; 真正面试的时候碰到, 只要不慌, 应该能做出来, 关键是如果之前的intuition被break了, 就要trace the error, 重新apply之前错误的逻辑, 想想为什么这个case你的逻辑就不对; 在此基础上收集思想, 来获得a closer intuition;

另外, 写的时候你每一个iteration对应的其实是一个index, 一个i, 但是你却要讨论的是一个downtick, 那么这个downtick的做右端点对应的分别是多少? 这个要时刻提醒自己一下;

这个是discussion上面一个所谓的greedy解法, 虽然我认为并不如我自己的解法:

@Hao-Cai said in [Java/C++] Simple greedy like solution with explanation:

This problem is like a greedy problem. When you find nums[i-1] > nums[i] for some i, you will prefer to change nums[i-1]'s value, since a larger nums[i] will give you more risks that you get inversion errors after position i. But, if you also find nums[i-2] > nums[i], then you have to change nums[i]'s value instead, or else you need to change both of nums[i-2]'s and nums[i-1]'s values.

Java version:

 public boolean checkPossibility(int[] nums) {  
        int cnt = 0;                                                                    //the number of changes  
        for(int i = 1; i < nums.length && cnt<=1 ; i++){  
            if(nums[i-1] > nums[i]){  
                cnt++;  
                if(i-2<0 || nums[i-2] <= nums[i])nums[i-1] = nums[i];                    //modify nums[i-1] of a priority  
                else nums[i] = nums[i-1];                                                //have to modify nums[i]  
            }  
        }  
        return cnt<=1;   
    }

C++ version:

bool checkPossibility(vector<int>& nums) {  
        int cnt = 0;                                                                    //the number of changes  
        for(int i = 1; i < nums.size() && cnt<=1 ; i++){  
            if(nums[i-1] > nums[i]){  
                cnt++;  
                if(i-2<0 || nums[i-2] <= nums[i])nums[i-1] = nums[i];                    //modify nums[i-1] of a priority  
                else nums[i] = nums[i-1];                                                //have to modify nums[i]  
            }  
        }  
        return cnt<=1;  
    }

这个思路本身其实总体是没有问题的, 看一看学一学也没毛病;

这个是另外一个类似我的, 不需要modify input的解法;

class Solution {  
    public boolean checkPossibility(int[] a) {  
        int modified = 0;  
        for (int i = 1, prev = a[0]; i < a.length; i++) {  
            if (a[i] < prev && modified++ > 0) return false;  
            if (a[i] < prev && i - 2 >= 0 && a[i - 2] > a[i]) continue;  
            prev = a[i];  
        }  
        return true;  
    }  
}

其实我想想他这个想法是比我的思路更直接的, 而且他这个思路可以认为是被modify的解法inspire过来的, 所以是有一个成长性的思路在里面的, 很不错;

这个题目还是太新了, 目前discussion并没有很多其他更好的解法, 暂时不管了;

Problem Description

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

Difficulty:Easy
Total Accepted:2K
Total Submissions:11.2K
Contributor: Stomach_ache
Companies
google
Related Topics
array