There is an integer matrix which has the following features:

The numbers in adjacent positions are different.

The matrix has n rows and m columns.

For all i < m, A[0][i] < A[1][i] && A[n - 2][i] > A[n - 1][i].

For all j < n, A[j][0] < A[j][1] && A[j][m - 2] > A[j][m - 1].

We define a position P is a peek if:

We define a position P is a peek if:

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]

Find a peak element in this matrix. Return the index of the peak.

1. nlogn思路

二分行或二分列，二分行来举例

选中间的一行（因为如果要除掉一半的区间就要选中间）

然后找到当前行的最大值（打一遍擂台）， 然后看上面和下面行当前列的值，

1. 如果上下都下， 则返回答案
2. 如果上小下大，上大下小，则除掉小的那半边 （因为大的那半边，一定不会再回来因为我们需要往上爬）
3. 如果都小，往哪边走都可以(一定有解）

public class Solution {
    /*
     * @param A: An integer matrix
     * @return: The index of the peak
     */
    public List<Integer> findPeakII(int[][] A) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) {
            return ans;
        }

        int start = 1;
        int end = A.length - 2;

        //System.out.println(end);
        while (start < end) {
            int mid = start + (end - start) / 2;
            int cur = findMax(A, mid);

            if (A[mid][cur] > A[mid - 1][cur] && A[mid][cur] > A[mid + 1][cur]) {
                ans.add(mid);
                ans.add(cur);
                return ans;
            } else if (A[mid][cur] < A[mid - 1][cur]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }

            // System.out.println(start);
            // System.out.println(end);
            // System.out.println((start + 1) < end);
        }

        ans.add(start);
        ans.add(findMax(A, start));
        return ans;



    }

    public int findMax(int[][] A, int mid) {
        int max = Integer.MIN_VALUE;
        int ans = 0;
        for (int i = 0; i < A[0].length; i++) {
            if (max < A[mid][i]) {
                max = A[mid][i];
                ans = i;
            }
        }
        return ans;
    }
}