描述

一個(gè)整數(shù)矩陣有如下一些特性：
相鄰的整數(shù)都是不同的
矩陣有 n 行 m 列。
對(duì)于所有的 i < m, 都有 A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i].
對(duì)于所有的 j < n, 都有 A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1].
我們定義一個(gè)位置 P 是一個(gè)峰，如果有 A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1]。
找出該矩陣的一個(gè)峰值元素，返回它的坐標(biāo)。

注意事項(xiàng)

可能會(huì)存在多個(gè)峰值，返回任意一個(gè)即可。

思路

從中間行的最大值往上或下尋找比該元素更大的值攀爬，從而使矩陣在 O(n) 的時(shí)間操作下規(guī)模減小了一半，然后在剛剛元素所在列尋找最大值，對(duì)當(dāng)前規(guī)模為原來一半的矩陣進(jìn)行重復(fù)的尋找操作

代碼

// O(m + n) 算法
// 利用 flag 來對(duì)行列進(jìn)行交替二分，flag = true 時(shí)二分行，flag = false 時(shí)二分列
// 每一次遞歸調(diào)用 x1, x2, y1, y2 都會(huì)更新
class Solution {
    /**
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    public List<Integer> find(int x1, int x2, int y1, int y2,
                              int[][] A, boolean flag) {
        
        if (flag) {
            int mid = x1 + (x2 - x1) / 2;
            int index = y1;
            for (int i = y1; i <= y2; ++i) {
                if (A[mid][i] > A[mid][index]) {
                    index = i;
                }
            }
                    
            if (A[mid - 1][index] > A[mid][index]) {
                return find(x1, mid - 1, y1, y2, A, !flag);
            }
            else if (A[mid + 1][index] > A[mid][index]) {
                return find(mid + 1, x2, y1, y2, A, !flag);
            }
            else {
                return new ArrayList<Integer>(Arrays.asList(mid, index));
            }
        } else {
            int mid = y1 + (y2 - y1) / 2;
            int index = x1;
            for (int i = x1; i <= x2; ++i) {
                if (A[i][mid] > A[index][mid]) {
                    index = i;
                }
            }
                    
            if (A[index][mid - 1] > A[index][mid]) {
                return find(x1, x2, y1, mid - 1, A, !flag); 
            }
            else if (A[index][mid + 1] > A[index][mid]) {
                return find(x1, x2, mid + 1, y2, A, !flag);
            }
            else {
                return new ArrayList<Integer>(Arrays.asList(index, mid));
            }
        }
    }
    
    public List<Integer> findPeakII(int[][] A) {
        int n = A.length;
        int m = A[0].length;
        return find(1, n - 2, 1, m - 2, A, true);
    }
}