1901. Find a Peak Element II

 一刷 07/2022

Version #1 Row Binary Search + Column Iteration

注意这里结束条件是 start <= end，因为当start == end的时候也要找到max

Time O(MlogN)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find a Peak Element II.

Memory Usage: 113.6 MB, less than 66.19% of Java online submissions for Find a Peak Element II.

class Solution {

    public int[] findPeakGrid(int[][] mat) {

        int rows = mat.length, cols = mat[0].length;

        int start = 0, end = rows - 1;

        while (start <= end) {

            int mid = start + (end - start) / 2;

            int[] midRow = mat[mid];

            int rowMaxIndex = 0;

            for (int i = 0; i < midRow.length; i++) {

                if (midRow[i] > midRow[rowMaxIndex]) {

                    rowMaxIndex = i;

                }

            }

            // mid is the row index, rowMaxIndex is the column index

            if ((mid - 1 < 0 || mat[mid -1][rowMaxIndex] < mat[mid][rowMaxIndex]) && (mid + 1 >= rows || mat[mid + 1][rowMaxIndex] < mat[mid][rowMaxIndex])) {

                return new int[]{mid, rowMaxIndex};

            }

            if (mid - 1 >= 0 && mat[mid - 1][rowMaxIndex] > mat[mid][rowMaxIndex]) {

                end = mid - 1;

            } else {

                start = mid + 1;

            }

        }

        return new int[0];

    }

}