LeetCode 240题：二维矩阵搜索II的BFS解法超时问题求助

题目要求 #

实现高效算法在m×n整数矩阵matrix中搜索目标值target，该矩阵满足以下特性：
每行整数从左到右升序排列；每列整数从上到下升序排列。
示例输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]，target = 5，输出：true

你的代码 #

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    if(matrix[0][0]>target){
        return false
    }
    const rows = matrix.length
    const cols = matrix[0].length
    const visited = Array(rows).fill(null).map((element)=> Array(cols).fill(false))
    let queue = []
    queue.push([0,0])
    while(queue.length>0){
        let [x, y] = queue.shift()
        visited[y][x] = true
        if(matrix[y][x] == target){
            return true
        }
        let direction
        if(matrix[y][x]>target){
            direction = [[x-1, y], [x, y-1]]
        }
        else{
            direction = [[x+1,y],[x, y+1]]
        }
        for(let i=0, _length = direction.length; i<_length; i++){
            if(direction[i][1]>=0 && direction[i][1] >=0 && direction[i][0]<=(cols-1) && direction[i][1]<=(rows-1)){
                if(!visited[direction[i][1]][direction[i][0]]){
                    queue.push(direction[i])
                }
            }
        }
    }
    return false
};

问题分析与改进方案 #

1. 为什么BFS不适合这个问题 #

这个矩阵的核心特性是每行升序、每列升序，但并非全局严格递增（比如左上角到右下角的路径不是单调的）。BFS是通用的网格搜索方法，最坏情况下时间复杂度为O(mn)——当target在矩阵右下角时，需要遍历几乎所有节点，对于大矩阵来说必然超时。

而利用矩阵的有序性，我们可以设计出时间复杂度为O(m+n)的线性遍历算法，每次遍历都能直接排除一整行或一整列，效率远高于BFS。

2. 你的代码中的具体问题 #

• shift()操作的性能瓶颈：JavaScript中数组的shift()方法是O(n)时间复杂度，每次弹出队列头部都会重新排列数组元素。当队列规模较大时，这个操作会导致严重的性能损耗。
• 方向选择逻辑冗余且有漏洞：当当前值大于target时，选择向左、向上走，但这两个方向的节点可能已经被访问过（或无需访问），而且没有利用矩阵特性排除整行/列；边界判断中direction[i][1]>=0 && direction[i][1] >=0是重复判断，应为direction[i][0]>=0和direction[i][1]>=0。
• 不必要的visited数组：基于矩阵的有序性，我们可以设计单向遍历路径（无需回头），完全不需要记录访问过的节点，这会额外消耗内存并增加判断开销。

3. 优化后的解法 #

利用矩阵右上角（或左下角）的特性：右上角的元素是当前行的最大值、当前列的最小值。每次比较后可以直接排除一行或一列：

var searchMatrix = function(matrix, target) {
    let row = 0;
    let col = matrix[0].length - 1;
    
    while (row < matrix.length && col >= 0) {
        const current = matrix[row][col];
        if (current === target) {
            return true;
        } else if (current > target) {
            // 当前值大于target，向左移动，排除当前列
            col--;
        } else {
            // 当前值小于target，向下移动，排除当前行
            row++;
        }
    }
    return false;
};

这个解法的时间复杂度为O(m+n)，空间复杂度为O(1)，完全符合高效要求，不会出现超时问题。

内容的提问来源于stack exchange，提问作者Pravin Poudel