[Lintcode] Find Peak Element 找峰值

摘要：找出该矩阵的一个峰值元素，返回他的坐标原题链接一维二分搜索复杂度时间空间思路最直观的方法是遍历整个矩阵，但这要的时间。

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)

最简单的做法，遍历数组找出比前后都大的元素。

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)

题目要求时间复杂度为O(logN)，logN时间的题目一般都是Heap，二叉树，分治法，二分搜索这些很“二”解法。这题是找特定元素，基本锁定二分搜索法。我们先取中点，由题意可知因为两端都是负无穷，有上坡就必定有一个峰，我们看中点的左右两边大小，如果向左是上坡，就抛弃右边，如果向右是上坡，就抛弃左边。直到两边都小于中间，就是峰了。

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;
    }
}

一个整数矩阵有如下一些特性：
相邻的整数都是不同的 矩阵有 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。
找出该矩阵的一个峰值元素，返回他的坐标

原题链接

时间 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)的时间。对于二维数组，我们也可以使用二分搜索法。比如，我们按照行二分搜索（意思是在1、2、3、4、5行中取得第3行），然后遍历这行找到这行的峰值，比如第3行是24。然后看24的上下两个元素的大小，这里24比19大，但是比25小，可知1、2行中肯定有答案（因为24到25是一个上坡，上坡方向必有解）。所以我们抛弃第3、4、5行，再在1、2行中重复这个二分搜索，直到找到结果。

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){
            //对行进行二分
            mid = min + ((max - min) >> 1);
            //找出中间行的峰值
            int col = findPeak(mid, A);
            //判断二分前进方向
            if(A[mid][col] < A[mid + 1][col]){
                min = mid + 1;
            } else if (A[mid][col] < A[mid - 1][col]){
                max = mid - 1;
            } else {
            //四周都较小则返回结果
                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

我们还可以依次对行和列都进行二分搜索，进一步降低时间复杂度。比如我们先选到第3行，找到24作为本行最大后，发现应该向上前进，所以在比24上方的区域，也就是完整的1、2行，对列进行二分，找到第三列（这个第三列是只有1、2行的第三列，3、4、5行已经被抛弃），找出第三列的两行中最大值25，发现左边的41大于25，所以3、4、5列被抛弃。现在还剩下前两行的前两列，再在这个区域对行二分，找出的是第1行，以此类推，最后当mid == min 时，结果肯定在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){
            //计算行的二分中点
            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;
            }
            //计算列的二分中点
            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;
    }
}