[Leetcode]240. Search a 2D Matrix II

这道题果然是升级版，思路不像他的弱化版那么好想了。虽然是排序但是排序拍的稍稍有点乱，要捋一捋。猛然醒悟，原来上面一篇说的不太好的O(n)的算法是这道题的解法。。。

先贴代码, AC答案：

public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
        //Two possible start point, bottom left and top right. Other two corner can not help us exclude numbers
        //Four edges all have limititions, only corner can make certain decision
        if(matrix == null || matrix.length == 0){
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        // i, j is the left bottom corner
        int i = m - 1;
        int j = 0;
        while(i>=0 && j<n){
            if(target > matrix[i][j]){
                j++;
            }
            else if(target < matrix[i][j]){
                i--;
            }
            else{
                return true;
            }
        }
        return false;     
    }
}

解题思想呢有点像dp。刚开始没理解思路的时候，上来就写，没找好四个角，出现了一个问题，if里面呢，不知道什么时候往左，什么时候往下，if里面还有个if，后来发现不对劲。写出来要O(n*n)。只有固定好了移动方向，才能是n，才能不枉费已经排好的顺序。

我们发现比左上角大没啥价值，一排都没缩小范围，右下角也一样。只有比左边界小的时候，能排除右下方所有行，就在自己右上方搜索就行了，当target比下边界大的时候呢，排除左上所有列。所以啊，左下方这个角，也就是矩形定点的信息量大大的。或者右上角，同理。左上角这哥们，不管target比他大，比他小，都能有一个确定的移动方向，右上同理。别的俩角不行。

代码尤其简单！秒过