当前位置：首页 > news >正文

二分查找题目：寻找峰值 II

news 来源：原创 2025/5/14 21:25:40

文章目录

题目
- 标题和出处
- 难度
- 题目描述
- - 要求
  - 示例
  - 数据范围
解法
- 思路和算法
- 证明
- 代码
- 复杂度分析

题目

标题和出处

标题：寻找峰值 II

出处：1901. 寻找峰值 II

难度

7 级

题目描述

要求

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

给定一个 $\texttt{m} \times \texttt{n}$ 的矩阵 $\texttt{mat}$ ，其中任意两个相邻元素均不相等，找出任意一个峰值元素 $\texttt{mat[i][j]}$ 并返回其位置 $\texttt{[i,j]}$ 。

可以假设整个矩阵周边环绕着一圈元素 $\texttt{-1}$ 。

要求时间复杂度是 $\texttt{O(m log n)}$ 或 $\texttt{O(n log m)}$ 。

示例

示例 1：

示例 1

输入： $\texttt{mat = [[1,4],[3,2]]}$
输出： $\texttt{[0,1]}$
解释： $\texttt{3}$ 和 $\texttt{4}$ 都是顶峰元素，所以 $\texttt{[1,0]}$ 和 $\texttt{[0,1]}$ 都是正确答案。

示例 2：

示例 2

输入： $\texttt{mat = [[10,20,15],[21,30,14],[7,16,32]]}$
输出： $\texttt{[1,1]}$
解释： $\texttt{30}$ 和 $\texttt{32}$ 都是顶峰元素，所以 $\texttt{[1,1]}$ 和 $\texttt{[2,2]}$ 都是正确答案。

数据范围

$\texttt{m} = \texttt{mat.length}$
$\texttt{n} = \texttt{mat[i].length}$
$\texttt{1} \le \texttt{m, n} \le \texttt{500}$
$\texttt{1} \le \texttt{mat[i][j]} \le \texttt{10}^\texttt{5}$
任意两个相邻元素均不相等

解法

思路和算法

这道题是「寻找峰值」的进阶，要求在矩阵中寻找峰值。

对于 $m$ 行 $n$ 列的矩阵，题目要求寻找峰值的时间复杂度是 $\log n)$ 或 $\log m)$ ，因此需要使用二分查找的做法寻找峰值。考虑矩阵每一行的最大值，其中一定存在一个最大值是峰值。在矩阵的行下标范围中执行二分查找，二分查找的次数是 $O(\log m)$ ，对于矩阵的每一行可以在 $O (n)$ 的时间内找到该行的最大值所在列，即每次二分查找需要 $O (n)$ 的时间，总时间复杂度是 $\log m)$ 。

考虑矩阵 $\textit{mat}$ 中的两个相邻行下标 $i$ 和 $j$ ，其中 $\le i, j < m$ 且 $j - i = 1$ ，用 $c$ 表示 $\textit{mat}[i]$ 中的最大值所在列下标。由于 $\textit{mat}[i][c] \ne \textit{mat}[j][c]$ ，因此 $\textit{mat}[i][c]$ 和 $\textit{mat}[j][c]$ 的大小关系是 $\textit{mat}[i][c] > \textit{mat}[j][c]$ 或 $\textit{mat}[i][c] < \textit{mat}[j][c]$ 。

当 $\textit{mat}[i][c] > \textit{mat}[j][c]$ 时，行下标范围 $[0, i]$ 中一定存在峰值；当 $\textit{mat}[i][c] < \textit{mat}[j][c]$ 时，行下标范围 $[j, m - 1]$ 中一定存在峰值。因此可以根据 $\textit{mat}[i][c]$ 和 $\textit{mat}[j][c]$ 的大小关系判断可能存在峰值的行下标范围，并在更小的范围内查找峰值。

基于上述思路，可以使用二分查找的做法寻找峰值。

用 $\textit{low}$ 和 $\textit{high}$ 分别表示二分查找的行下标范围的下界和上界，初始时 $\textit{low}$ 和 $\textit{high}$ 分别为数组的最小行下标和最大行下标。每次查找时，取 $\textit{mid}$ 为 $\textit{low}$ 和 $\textit{high}$ 的平均数向下取整，将 $\textit{mat}[\textit{mid}]$ 中的最大值所在列下标记为 $\textit{maxIndex}$ ，比较 $\textit{mat}[\textit{mid}][\textit{maxIndex}]$ 和 $\textit{mat}[\textit{mid} + 1][\textit{maxIndex}]$ 的大小关系（注意当 $\textit{low} < \textit{high}$ 时， $\textit{mid} \le m - 2$ ，因此行下标 $\textit{mid} + 1$ 不会超出矩阵行下标范围），判断可能存在峰值的下标范围，调整查找的下标范围。

如果 $\textit{mat}[\textit{mid}][\textit{maxIndex}] > \textit{mat}[\textit{mid} + 1][\textit{maxIndex}]$ ，则行下标范围 $[\textit{low}, \textit{mid}]$ 中可能存在峰值，在该行下标范围中继续查找。
如果 $\textit{mat}[\textit{mid}][\textit{maxIndex}] < \textit{mat}[\textit{mid} + 1][\textit{maxIndex}]$ ，则行下标范围 $[\textit{mid} + 1, \textit{high}]$ 中可能存在峰值，在该行下标范围中继续查找。

当 $\textit{low} = \textit{high}$ 时，查找结束，此时 $\textit{mat}[\textit{low}]$ 的最大值即为峰值，找到峰值并返回其位置。

证明

为了证明上述二分查找做法的正确性，对于 $\le i, j < m$ 且 $j - i = 1$ ， $\textit{mat}[i][c]$ 是 $\textit{mat}[i]$ 的最大值，需要证明：当 $\textit{mat}[i][c] > \textit{mat}[j][c]$ 时，行下标范围 $[0, i]$ 中一定存在峰值；当 $\textit{mat}[i][c] < \textit{mat}[j][c]$ 时，行下标范围 $[j, m - 1]$ 中一定存在峰值。可以使用反证法证明。

当 $\textit{mat}[i][c] > \textit{mat}[j][c]$ 时，假设行下标范围 $[0, i]$ 中不存在峰值。由于 $\textit{mat}[i][c]$ 不是峰值，因此 $\textit{mat}[i][c] < \textit{mat}[i - 1][c]$ ， $\textit{mat}[i - 1]$ 的最大值一定大于 $\textit{mat}[i]$ 的最大值。从行下标 $i - 1$ 向上遍历矩阵 $\textit{mat}$ ，对于每个行下标 $k$ ， $\textit{mat}[k]$ 的最大值都不是峰值，因此每一行的最大值都小于上一行同列的元素，每一行的最大值都小于上一行的最大值。遍历到 $\textit{mat}[0]$ 时， $\textit{mat}[0]$ 的最大值严格大于其左边、右边和下边的相邻元素。由于矩阵中的元素都是正整数且矩阵周围的元素都是 $- 1$ ，因此 $\textit{mat}[0]$ 的最大值严格大于其所有的相邻元素， $\textit{mat}[0]$ 的最大值即为峰值。由此可以得到行下标范围 $[0, i]$ 中一定存在峰值。

当 $\textit{mat}[i][c] < \textit{mat}[j][c]$ 时，同理可知行下标范围 $[j, m - 1]$ 中一定存在峰值。

代码

class Solution {public int[] findPeakGrid(int[][] mat) {int m = mat.length;int low = 0, high = m - 1, maxIndex = 0;while (low < high) {int mid = low + (high - low) / 2;maxIndex = getMaxIndex(mat[mid]);if (mat[mid][maxIndex] > mat[mid + 1][maxIndex]) {high = mid;} else {low = mid + 1;}}maxIndex = getMaxIndex(mat[low]);return new int[]{low, maxIndex};}public int getMaxIndex(int[] row) {int index = 0, maxNum = 0;int n = row.length;for (int i = 0; i < n; i++) {if (row[i] > maxNum) {maxNum = row[i];index = i;}}return index;}
}

复杂度分析

时间复杂度： $\log m)$ ，其中 $m$ 和 $n$ 分别是数组 $\textit{mat}$ 的行数和列数。二分查找的次数是 $O(\log m)$ ，每次二分查找需要 $O (n)$ 的时间，时间复杂度是 $\log m)$ 。
空间复杂度： $O (1)$ 。