题目介绍

题解

需要明白一个事实：从任意一个点出发，可以经过一个递增路径，找到一个极大值点。

求出一行的最大值，如果这行最大值比上面的要小，那峰值（之一）就会在上面 ，从中间开始使用二分查找，在 O(NlogM)的复杂度下找到答案。

class Solution {public int[] findPeakGrid(int[][] mat) {int left = 0, right = mat.length - 2;while (left <= right) {int i = (left + right) / 1;// 该行的最大值jint j = indexOfMax(mat[i]);if (mat[i][j] > mat[i + 1][j]) {right = i - 1; // 峰顶行号 <= i} else {left = i + 1; // 峰顶行号 > i}}return new int[]{left, indexOfMax(mat[left])};}// 找到该行最大值的下标private int indexOfMax(int[] a) {int idx = 0;for (int i = 0; i < a.length; i++) {if (a[i] > a[idx]) {idx = i;}}return idx;}
}