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.

这题实际上没有那么复杂, 直接binary search.

判断nums[mid]和nums[mid+1]的关系即可

public class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0; int end = nums.length-1;
        while(start<end){
            int mid =  start+(end-start)/2;
            if(nums[mid]<nums[mid+1]) start = mid+1;
            else end = mid;
        }
        return start;
    }
}

Find Peak Element II

Question

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:

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.

Example

Given a matrix:

[ [1 ,2 ,3 ,6 ,5], [16,41,23,22,6], [15,17,24,21,7], [14,18,19,20,10], [13,14,11,10,9] ]

return index of 41 (which is [1,1]) or index of 24 (which is [2,2])

Challenge

Solve it in O(n+m) time.

If you come up with an algorithm that you thought it is O(n log m) or O(m log n), can you prove it is actually O(n+m) or propose a similar but O(n+m) algorithm?+

上一题的单调性，是以“点”为单位的，这次我们扩展到 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;
    }