描述

给定一个整数矩阵 A, 它有如下特性: 相邻的整数不同 矩阵有 n 行 m 列，n 和 m 不会小于 3 。 对于所有的 i < n, 都有 A[i][0] < A[i][1] && A[i][m – 2] > A[i][m – 1] 对于所有的 j < m, 都有 A[0][j] < A[1][j] && A[n – 2][j] > A[n – 1][j] 我们定义一个位置 [i,j] 是峰值, 当且仅当它满足:

  A[i][j] > A[i + 1][j] && A[i][j] > A[i - 1][j] &&    A[i][j] > A[i][j + 1] && A[i][j] > A[i][j - 1] 

找到该矩阵的一个峰值元素, 返回它的坐标. 保证至少存在一个峰值, 而如果存在多个峰值, 返回任意一个即可.

在线评测地址

样例 1:

输入:      [       [1, 2, 3, 6,  5],       [16,41,23,22, 6],       [15,17,24,21, 7],       [14,18,19,20,10],       [13,14,11,10, 9]     ] 输出: [1,1] 解释: [2,2] 也是可以的. [1,1] 的元素是 41, 大于它四周的每一个元素 (2, 16, 23, 17). 

样例 2：

输入:      [       [1, 5, 3],       [4,10, 9],       [2, 8, 7]     ] 输出: [1,1] 解释: 只有这一个峰值 

挑战

O(n+m) 的时间复杂度. 如果你 认为 你使用了 O(nlogm) 或 O(mlogn) 的算法, 能否证明它的复杂度其实是 O(n+m)? 或者想一个类似的算法但是复杂度是 O(n+m)？

解题思路

峰值不是最大值，只是比四个方向上的数值都大，是局部性的最值。 对于每一个点，它总能属于某一座山峰（可以不止一座）。 找峰值可以想象成爬山，总是要不断的从低处向高处移动，这样移动到最后一定是峰值。

代码思路

在图上随机取一点，若有相邻位置比当前点大则向该相邻位置移动，直到当前点成为峰值。 最坏情况是螺旋式上升，且随机在了起点位置，那么就要爬升一半的点 1 2 3 4 5 0 0 0 0 6 15 16 17 0 7 14 0 0 0 8 13 12 11 10 9 如果遇到最坏的情况，我们可以通过当爬升超过一定距离后重新随机一个点，使得相对平均效率较高

复杂度分析

NN 表示行数，MM 表示列数 空间复杂度：O(1) 平均时间复杂度：O(N+M)

public class Solution {      /*       * @param A: An integer matrix       * @return: The index of the peak       */      public List<Integer> findPeakII(int[][] A) {          int n = A.length;          int m = A[0].length;          int now_x, now_y, next_x, next_y;          //这里初始位置选择为中心位置          now_x = n / 2;          now_y = m / 2;          while (1 == 1) {              next_x = now_x;              next_y = now_y;              //四个方向上若有比当前位置大的，则向该方向移动              if (now_x + 1 < n && A[now_x + 1][now_y] > A[next_x][next_y]) {                  next_x = now_x + 1;                  next_y = now_y;              }else if (now_x - 1 >= 0 && A[now_x - 1][now_y] > A[next_x][next_y]) {                  next_x = now_x - 1;                  next_y = now_y;              }else if (now_y + 1 < m && A[now_x][now_y + 1] > A[next_x][next_y]) {                  next_x = now_x;                  next_y = now_y + 1;              }else if (now_y-1 >= 0 && A[now_x][now_y - 1] > A[next_x][next_y]) {                  next_x = now_x;                  next_y = now_y - 1;              }              //若四个方向上都比当前位置小，即为峰值直接返回答案              if (next_x == now_x && next_y == now_y) {                  return new ArrayList<Integer>(Arrays.asList(now_x, now_y));              }              now_x = next_x;              now_y = next_y;          }      }  }  

更多题解参考

大佬有話說 (0)