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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/binary_search_lei/find_peak_element_i_and_ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.