题目

思路

从右上角 (0, n - 1) 作为起点走楼梯，因为：

  • 左边都更小
  • 下边都更大

从这个点可以一次排除一整行或者一整列。

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            int x = matrix[i][j];
            if (x == target) {
                return true;
            }
            if (x > target) {
                j --;
            } else {
                i ++;
            }
        }
        return false;
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1

        while i < m and j >= 0:
            x = matrix[i][j]
            if x == target:
                return True
            if x > target:
                j -= 1
            else:
                i += 1
        return False