> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/binary_search_lei/find_peak_element_i_and_ii.md).

# Find Peak Element I & II

## [Find Peak Element](https://leetcode.com/problems/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.

```java
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](http://www.lintcode.com/en/problem/find-peak-element-ii/#)

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

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

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

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

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