【Leetcode】1901. Find a Peak Element II

题目地址：

https://leetcode.com/problems/find-a-peak-element-ii/description/

给定一个$m\times n$的二维矩阵$A$，题目保证每个数字四个方向上的相邻数字一定不同。求一个位置，该位置比其相邻的数都更大。返回其坐标。如果不存在则返回$(-1,-1)$。

思路是二分。我们将所有行看成一个整体，对这$m$行进行二分，分到一行的时候，看一下这行的最大值，如果这个最大值已经满足条件了，则直接返回答案；如果不满足，说明这个数$x$比其上下其中一个小，不妨设其比其上的那个数小，那么可以断定，如果有解，其中必然有一个解在上半部分（可以这样想，我们可以沿着$x$上面那个数继续走，每次就走上升的路径，这个路径一定不会回到$x$所在行的，因为$x$就是其所在行的最大值），那么我们就能将下半部分直接排除了。其实我们是可以证明解一定存在的，证明很显然，只要随便取一个起点然后沿着上升路径走就行了。代码如下：

class Solution {
 public:
  vector<int> findPeakGrid(vector<vector<int>>& A) {
    vector<int> res;
    int m = A.size(), n = A[0].size();
    int l = 0, r = m - 1;
    int max_col = 0;
    while (l < r) {
      int mid = l + (r - l >> 1);
      for (int i = 0; i < n; i++)
        if (A[mid][i] > A[mid][max_col]) max_col = i;
      if ((!mid || A[mid][max_col] > A[mid - 1][max_col]) &&
          (mid == m - 1 || A[mid][max_col] > A[mid + 1][max_col]))
        return {mid, max_col};

      if (mid && A[mid][max_col] < A[mid - 1][max_col])
        r = mid;
      else
        l = mid + 1;
    }
	// 解一定存在
	return {l, max_col};
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度$O(n\log m)$，空间$O(1)$。