Medium

题目描述

二维网格中的峰值是指严格大于其相邻四个方向（左、右、上、下）所有元素的元素。

给你一个 0 索引 的 m x n 矩阵 mat，其中任意两个相邻元素都不相等，找出任意一个峰值 mat[i][j] 并返回长度为 2 的数组 [i,j]。

你可以假设整个矩阵的四周环绕着一圈数值为 -1 的元素。

要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法。

示例 1：

输入：mat = [[1,4],[3,2]]
输出：[0,1]
解释：3 和 4 都是峰值，所以 [1,0] 和 [0,1] 都是可接受的答案。

示例 2：

输入：mat = [[10,20,15],[21,30,14],[7,16,32]]
输出：[1,1]
解释：30 和 32 都是峰值，所以 [1,1] 和 [2,2] 都是可接受的答案。

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 500
  • 1 <= mat[i][j] <= 10^5
  • 矩阵中任意两个相邻元素都不相等。

解题思路

这是一道需要在二维矩阵中寻找峰值的问题，要求时间复杂度为 O(m log(n)) 或 O(n log(m))。

核心思路：二分查找 + 降维

我们可以将二维问题转化为一维问题来解决。具体步骤如下：

  1. 选择较大的维度进行二分：假设列数大于行数，我们对列进行二分查找
  2. 找中间列的最大值：在当前搜索范围的中间列中，找到该列的最大值及其位置
  3. 判断峰值方向：
    • 如果该最大值比左邻居大且比右邻居大，则它就是峰值
    • 如果左邻居更大，说明峰值在左半部分，递归搜索左半部分
    • 如果右邻居更大，说明峰值在右半部分，递归搜索右半部分

关键洞察：

  • 由于中间列的最大值已经比该列所有其他元素大，我们只需要检查它的左右邻居
  • 如果左右邻居都比它小，它就是峰值
  • 如果某一侧的邻居比它大，那么峰值一定在那一侧（因为边界是-1，必然存在峰值）

这种方法的时间复杂度是 O(m log(n))，其中每次二分需要 O(m) 时间找到列最大值，总共需要 O(log n) 次二分。

代码实现

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int left = 0, right = n - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int maxRow = 0;
            
            // 找到中间列的最大值
            for (int i = 0; i < m; i++) {
                if (mat[i][mid] > mat[maxRow][mid]) {
                    maxRow = i;
                }
            }
            
            // 检查左右邻居
            int leftVal = (mid > 0) ? mat[maxRow][mid - 1] : -1;
            int rightVal = (mid < n - 1) ? mat[maxRow][mid + 1] : -1;
            
            if (mat[maxRow][mid] > leftVal && mat[maxRow][mid] > rightVal) {
                return {maxRow, mid};
            } else if (leftVal > mat[maxRow][mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return {-1, -1}; // 不会到达这里
    }
};

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        left, right = 0, n - 1
        
        while left <= right:
            mid = (left + right) // 2
            max_row = 0
            
            # 找到中间列的最大值
            for i in range(m):
                if mat[i][mid] > mat[max_row][mid]:
                    max_row = i
            
            # 检查左右邻居
            left_val = mat[max_row][mid - 1] if mid > 0 else -1
            right_val = mat[max_row][mid + 1] if mid < n - 1 else -1
            
            if mat[max_row][mid] > left_val and mat[max_row][mid] > right_val:
                return [max_row, mid]
            elif left_val > mat[max_row][mid]:
                right = mid - 1
            else:
                left = mid + 1
        
        return [-1, -1]  # 不会到达这里

public class Solution {
    public int[] FindPeakGrid(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        int left = 0, right = n - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int maxRow = 0;
            
            // 找到中间列的最大值
            for (int i = 0; i < m; i++) {
                if (mat[i][mid] > mat[maxRow][mid]) {
                    maxRow = i;
                }
            }
            
            // 检查左右邻居
            int leftVal = (mid > 0) ? mat[maxRow][mid - 1] : -1;
            int rightVal = (mid < n - 1) ? mat[maxRow][mid + 1] : -1;
            
            if (mat[maxRow][mid] > leftVal && mat[maxRow][mid] > rightVal) {
                return new int[] {maxRow, mid};
            } else if (leftVal > mat[maxRow][mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return new int[] {-1, -1}; // 不会到达这里
    }
}

var findPeakGrid = function(mat) {
    const m = mat.length, n = mat[0].length;
    let left = 0, right = n - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let maxRow = 0;
        
        // 找到中间列的最大值
        for (let i = 0; i < m; i++) {
            if (mat[i][mid] > mat[maxRow][mid]) {
                maxRow = i;
            }
        }
        
        // 检查左右邻居
        const leftVal = (mid > 0) ? mat[maxRow][mid - 1] : -1;
        const rightVal = (mid < n - 1) ? mat[maxRow][mid + 1] : -1;
        
        if (mat[maxRow][mid] > leftVal && mat[maxRow][mid] > rightVal) {
            return [maxRow, mid];
        } else if (leftVal > mat[maxRow][mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return [-1, -1]; // 不会到达这里
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m log n)二分查找需要 log n 次迭代，每次需要 O(m) 时间找列最大值
空间复杂度O(1)只使用常数额外空间

相关题目