摘要：找出該矩陣的一個峰值元素，返回他的坐標(biāo)原題鏈接一維二分搜索復(fù)雜度時間空間思路最直觀的方法是遍歷整個矩陣，但這要的時間。

A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
click to show spoilers.
Note: Your solution should be in logarithmic complexity.

原題鏈接

時間 O(N) 空間 O(1)

最簡單的做法，遍歷數(shù)組找出比前后都大的元素。

public class Solution {
    public int findPeakElement(int[] nums) {
        for(int i = 1; i < nums.length-1; i++){
            if(nums[i] > nums[i+1] && nums[i] > nums[i-1]){
                return i;
            }
        }
        return nums.length <= 1 || nums[0] > nums[1] ? 0 : nums.length-1;
    }
}

時間 O(logN) 空間 O(1)

題目要求時間復(fù)雜度為O(logN)，logN時間的題目一般都是Heap，二叉樹，分治法，二分搜索這些很“二”解法。這題是找特定元素，基本鎖定二分搜索法。我們先取中點(diǎn)，由題意可知因為兩端都是負(fù)無窮，有上坡就必定有一個峰，我們看中點(diǎn)的左右兩邊大小，如果向左是上坡，就拋棄右邊，如果向右是上坡，就拋棄左邊。直到兩邊都小于中間，就是峰了。

public class Solution {
    public int findPeakElement(int[] nums) {
        for(int min = 0, max = nums.length -1, mid = max / 2 ; min < max ; mid = (min + max) / 2){
            if(min == mid) return nums[min] < nums[max] ? max : min;
            min = nums[mid] < nums[mid+1] ? mid : min;
            max = nums[mid] > nums[mid+1] ? mid : max; 
        }
        return 0;
    }
}

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

原題鏈接

時間 O(MlogN) 空間 O(1)

1    2    3    4    5
16    41    25    22    6
15    17    24    21    7
14    18    19    20    8
13    12    11    10    9

最直觀的方法是遍歷整個矩陣，但這要O(MN)的時間。對于二維數(shù)組，我們也可以使用二分搜索法。比如，我們按照行二分搜索（意思是在1、2、3、4、5行中取得第3行），然后遍歷這行找到這行的峰值，比如第3行是24。然后看24的上下兩個元素的大小，這里24比19大，但是比25小，可知1、2行中肯定有答案（因為24到25是一個上坡，上坡方向必有解）。所以我們拋棄第3、4、5行，再在1、2行中重復(fù)這個二分搜索，直到找到結(jié)果。

class Solution {
    public List findPeakII(int[][] A) {
        // write your code here
        List res = new ArrayList();
        int min = 0, max = A.length - 1, mid = max / 2;
        while(min <= max){
            //對行進(jìn)行二分
            mid = min + ((max - min) >> 1);
            //找出中間行的峰值
            int col = findPeak(mid, A);
            //判斷二分前進(jìn)方向
            if(A[mid][col] < A[mid + 1][col]){
                min = mid + 1;
            } else if (A[mid][col] < A[mid - 1][col]){
                max = mid - 1;
            } else {
            //四周都較小則返回結(jié)果
                res.add(mid);
                res.add(col);
                return res;
            }
        }
        return res;
    }
    
    private int findPeak(int row, int[][] A){
        int peak = 0;
        for(int i = 1; i < A[row].length; i++){
            if(A[row][i]>A[row][peak]){
                peak = i;
            }
        }
        return peak;
    }
}

時間 O(2M+N) 空間 O(1)

1    2    3    4    5
16    41    25    22    6
15    17    24    21    7
14    18    19    20    8
13    12    11    10    9

我們還可以依次對行和列都進(jìn)行二分搜索，進(jìn)一步降低時間復(fù)雜度。比如我們先選到第3行，找到24作為本行最大后，發(fā)現(xiàn)應(yīng)該向上前進(jìn)，所以在比24上方的區(qū)域，也就是完整的1、2行，對列進(jìn)行二分，找到第三列（這個第三列是只有1、2行的第三列，3、4、5行已經(jīng)被拋棄），找出第三列的兩行中最大值25，發(fā)現(xiàn)左邊的41大于25，所以3、4、5列被拋棄。現(xiàn)在還剩下前兩行的前兩列，再在這個區(qū)域?qū)π卸?，找出的是?行，以此類推，最后當(dāng)mid == min 時，結(jié)果肯定在min和max之中。

class Solution {
    public List findPeakII(int[][] A) {
        // write your code here
        List res = new ArrayList();
        //初始化行的二分邊界，還有列的二分邊界
        int rowmin = 0, rowmax = A.length - 1, rowmid = rowmax / 2;
        int colmin = 0, colmax = A[0].length - 1, colmid = colmax / 2;
        while(rowmin <= rowmax && colmin <= colmax){
            //計算行的二分中點(diǎn)
            rowmid = rowmin + ((rowmax - rowmin) >> 1);
            int rowpeak = findRowPeak(rowmid, A, colmin, colmax);
            if(A[rowmid][rowpeak] < A[rowmid + 1][rowpeak]){
                rowmin = rowmid + 1;
            } else if (A[rowmid][rowpeak] < A[rowmid - 1][rowpeak]){
                rowmax = rowmid - 1;
            } else {
                res.add(rowmid);
                res.add(rowpeak);
                return res;
            }
            //計算列的二分中點(diǎn)
            colmid = colmin + ((colmax - colmin) >> 1);
            int colpeak = findColPeak(colmid, A, rowmin, rowmax);
            if(A[colpeak][colmid] < A[colpeak][colmid + 1]){
                colmin = colmid + 1;
            } else if (A[colpeak][colmid] < A[colpeak][colmid - 1]){
                colmax = colmid - 1;
            } else {
                res.add(colpeak);
                res.add(colmid);
                return res;
            }
        }
        return res;
    }
    
    private int findRowPeak(int row, int[][] A, int start, int end){
        int peak = 0;
        for(int i = start; i <= end; i++){
            if(A[row][i]>A[row][peak]){
                peak = i;
            }
        }
        return peak;
    }
    
    private int findColPeak(int col, int[][] A, int start, int end){
        int peak = 0;
        for(int i = start; i <= end; i++){
            if(A[i][col]>A[peak][col]){
                peak = i;
            }
        }
        return peak;
    }
}