Find Peak Element I & II

Find Peak Element

这题有两个重要条件：

• 相邻数字绝不重复

• 数组两端有 -Inf 做 padding

这就意味着在这样的给定条件下，区间 [0, n - 1] 一定存在一个 peak. 我们需要做的，就是利用 binary search 逐渐缩小这个有效区间的大小。

对于 nums[mid]:

• 如果检查其相邻元素，发现 mid 为单调上升，那么 mid 自己可以替代数组一端的 -Inf 作用，自己作为新区间起点的 padding，因为 [mid + 1, right] 区间内一定有 peak;

• 同理，如果 mid 处于一个单调下降的位置，那么 mid 自己可以取代原本的右侧 padding，[left, mid - 1] 区间内一定有 peak;

• 如果两边的元素都比 nums[mid] 大，那么两边都有 peak.

• 如果两边的元素都比 nums[mid] 小，mid 自己就是 peak.

public class Solution {
    public int findPeakElement(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        if(nums.length == 1) return 0;

        int left = 0;
        int right = nums.length - 1;

        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]){
                // nums[mid] is valid peak
                return mid;
            } else if(nums[mid - 1] < nums[mid] && nums[mid] < nums[mid + 1]){
                // nums[mid] is on an increasing trend
                left = mid;
            } else if(nums[mid - 1] > nums[mid] && nums[mid] > nums[mid + 1]){
                // nums[mid] is on a decreasing trend
                right = mid;
            } else {
                // nums[mid] is smaller than its neighbor, both directions have peak
                right = mid;
            }
        }

        return (nums[left] < nums[right]) ? right: left;
    }
}

Find Peak Element II

上一题的单调性，是以“点”为单位的，这次我们扩展到 2D array，就要开始以 “行 / 列” 为单位了。

初始条件是类似的：最外围的元素都小于里面，相当于做了一个 padding，同时相邻元素不相等，保证了矩阵里面一定存在 peak. 我们要做的，就是缩小需要查找的矩阵范围。

关键在于 ： 用当前行 / 列最大值的位置，代表整行 / 列。

• 在“灌水”问题里，一个一维数组某个区间内的水位，取决于两端最小值；二维矩阵里，水位也取决于 “木桶” 里面最短的那块板。

• 在“山峰”问题里，一个一维数组里，山峰的位置取决于里面的最大值，或局部最大值；在二维矩阵里，一行的 max 决定了这行所能达到的最高高度，在和相邻元素进行比较时，相邻元素若比 max 大，则 max 所属的行列，就饿一定可以做为新的 padding 边界，把这种单调性传递下去。

    public List<Integer> findPeakII(int[][] A) {
        // write your code here
        List<Integer> list = new ArrayList<>();
        int left = 1;
        int right = A[0].length - 2;
        while(left <= right){
            int mid = left + (right - left) / 2;
            int index = getColMaxIndex(A, mid);
            if(A[index][mid] < A[index][mid - 1]){
                right = mid - 1;
            } else if(A[index][mid] < A[index][mid + 1]){
                left = mid + 1;
            } else {
                list.add(index);
                list.add(mid);
                return list;
            }
        }
        return list;
    }

    private int getColMaxIndex(int[][] A, int col){
        int index = 0;
        int max = A[0][col];
        for(int i = 1; i < A.length - 1; i++){
            if(A[i][col] > max){
                max = A[i][col];
                index = i;
            }
        }
        return index;
    }