LeetCode 240. 搜索二维矩阵 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：Z 字形搜索（推荐）
相似题目

题目描述

✅ 240. 搜索二维矩阵 II

思路分析

解法一：Z 字形搜索（推荐）

核心思路：

矩阵特性：每行从左到右递增，每列从上到下递增。选取右上角作为起点，因为它是行内最大值、列内最小值，形成天然的决策节点：

从右上角 (0, n-1) 出发，令 i = 0，j = n-1

若 matrix[i][j] == target：直接返回 true

若 matrix[i][j] > target：当前值偏大，向左移动（j--），排除整列

若 matrix[i][j] < target：当前值偏小，向下移动（i++），排除整行

每步必然排除一整行或一整列，最多走 m + n - 1 步

左下角同样可行（规则对称：偏大则向上，偏小则向右）；左上角和右下角无法保证每步排除行或列，不可选。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为矩阵的行数和列数

空间复杂度：O(1)，只使用了两个指针

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 从右上角出发：行最大值 + 列最小值，形成决策节点
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                // 当前值偏大，向左排除当前列
                j--;
            } else {
                // 当前值偏小，向下排除当前行
                i++;
            }
        }
        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    m, n := len(matrix), len(matrix[0])
    // 从右上角出发：行最大值 + 列最小值，形成决策节点
    i, j := 0, n-1
    for i < m && j >= 0 {
        if matrix[i][j] == target {
            return true
        } else if matrix[i][j] > target {
            // 当前值偏大，向左排除当前列
            j--
        } else {
            // 当前值偏小，向下排除当前行
            i++
        }
    }
    return false
}

相似题目

题目	难度	考察点
74. 搜索二维矩阵	中等	行列严格递增，整体可二分
378. 有序矩阵中第 K 小的元素	中等	二分 + Z 字计数
668. 乘法表中第 k 小的数	困难	二分 + 计数
1351. 统计有序矩阵中的负数	简单	Z 字搜索变体
329. 矩阵中的最长递增路径	困难	矩阵 DFS + 记忆化

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/47047341