描述
给定一个整数矩阵 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;

        }

    }

}

更多题解参考：九章官网solution