leetcode 上的 peak finding 问题汇总
date
Nov 17, 2022
slug
peak-finding-leetcode
status
Published
tags
算法
summary
巧妙利用二分解题
type
Post
题目852. 山脉数组的峰顶索引方法1 暴力方法2 二分162. 寻找峰值方法1 暴力方法2 二分方法3 改进的暴力方法4 改进的二分74. 搜索二维矩阵方法1 暴力方法2 二分方法3 利用数组特性总结
题目
一共三道，每道题之间互相有联系
题目虽然没有保证 distinct，不过我们仍然可以用 divide and conquer 的思想尝试解题
852. 山脉数组的峰顶索引
方法1 暴力
读题，数据范围很小，直接遍历即可
这里有一个技巧，我们不需要真的去判断
A[i - 1], A[i], A[i + 1] 的关系，我们只需要找到第一个A[i] > A[i + 1]的i即可，因为这个i必然满足A[i - 1] < A[i]class Solution {
public int peakIndexInMountainArray(int[] A) {
for(int i = 1; i<A.length-1; i++){
if(A[i]>A[i+1])
return i;
}
return -1;
}
}
方法2 二分
二分查找的思想，山脉数组总是一个先上升后下降的趋势，那么按照二分的思想，每次取得mid进行判断
- mid就是山顶，返回mid
- mid处于局部上升的区间，返回右边区间的二分
- mid处于局部下降的区间，返回左边区间的二分
由此可以写出代码：
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int i = 1, j = n - 2;
while (i < j) {
int m = i + j >> 1;
if (arr[m + 1] < arr[m] && arr[m] > arr[m - 1]) {
return m;
} else {
if (arr[m + 1] > arr[m]) i = m + 1;
else j = m - 1;
}
}
return i;
}
}特别的，由于题目输入保证有解，我们可以初始化边界为 1 和 n - 2
162. 寻找峰值
就是之前提到的1D-finding问题，不过在leetcode上面可以做得更巧妙
方法1 暴力
自然而然就想到的做法
class Solution {
public int findPeakElement(int[] a) {
// 特殊判断
if (a.length == 0)
return -1;
if (a.length == 1)
return 0;
// 判断是否在边界
if (a[0] > a[1])
return 0;
else if (a[a.length - 1] > a[a.length - 1 - 1])
return a.length - 1;
// 不在边界就一定在中间
for (int i = 1; i < a.length - 1; i++) {
if (a[i] > a[i - 1] && a[i] > a[i + 1])
return i;
}
return -1;
}
}
方法2 二分
之前的文章我们分析过了，如果一个数组是
distinct的，那么这个数组至少会有一个峰值，且如果峰值的下标i不属于，那么峰值一定会出现在数组A的起始或者末尾，基于上述的结论，二分法在distinct的数组里面一定能找到峰值，我们不断往更大值的方向走就行了。class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length, i = 0, j = n - 1, m = i + j >> 1;
if (n == 1) return 0;
while (i < j ) {
m = i + j >> 1;
if (m == 0 || m == n - 1) break; // 边界条件提前退出
if (nums[m - 1] < nums[m] && nums[m] > nums[m + 1]) {
return m;
} else {
if (nums[m - 1] > nums[m + 1]) j = m - 1;
else i = m + 1;
}
}
if (m == 0) return nums[m] > nums[m + 1] ? m : m + 1;
else if (m == n - 1) return nums[m] > nums[m - 1] ? m : m - 1;
return i; // 非边界条件，正常返回i
}
}方法3 改进的暴力
由山脉数组这道题推导得来的结论
其实这种严格不重复的数组不外乎就四种形状
- 一直上升
- 一直下降
- 先上升后下降
- 先下降再上升
任何更复杂的数组，它的局部一定能找到上述形状，既然局部存在着上述形状，那么一定会存在峰值，所以我们可以分析这四种形状来解决问题
基于这个性质，我提出假设：
我们使i=0，然后从第一个元素开始比较，只需要比较第i个元素和第i+1个元素的大小即可对于假设的证明，我们使用反证法：
对于i属于0到A.length-1，当A[i]>A[i+1]的时候，A[i]一定是峰值。 这是因为如果A[i]不是峰值，那么必定有A[i-1]>A[i]，此时如果A[i-1]是峰值就不会遍历到A[i]，所以A[i-1]不是峰值，继续往上推导，得出结论A[0]一定大于A[1]，否则A[1]是峰值，但是A[1]不是，所以A[0]一定大于A[1]，于是A[0]是峰值，但是A[0]必然不是峰值，因为已经遍历到A[i]，所以可以得出A[0],A[1]...A[i-1]一定是小于A[i]的，反证法得出A[i]一定是峰值
由上我们可以得出更加简洁的暴力法
class Solution {
public int findPeakElement(int[] nums) {
int i=0;
for(;i<nums.length-1;i++){
if(nums[i]>nums[i+1]){
return i;
}
}
return i;
}
}
方法4 改进的二分
我们再继续讨论一下二分法能否用在这个问题上，对于nums，我们随机取得一个下标mid，，当nums[mid]同时满足
nums[mid-1]<nums[mid]<nums[mid+1]的时候，mid对应了一个峰值。但是经过上述的讨论我们发现，改进的暴力法只需要比较nums[mid]和nums[mid+1]的大小即可，由此我们先尝试写出二分的三个步骤，再验证是否正确。
三个步骤就是：满足条件（二分边界），往左二分，往右二分
取mid
- 如果
nums[mid]>nums[mid+1]，此时需要判断nums[mid-1]与nums[mid]的关系，需要往左边二分，由于nums[mid]有可能是峰顶，所以我们往左边二分的区间是[left,mid]
- 如果
nums[mid]<nums[mid+1]，那么nums[mid]必然不是峰顶，而numd[mid+1]是峰顶的可能性存在，所以我们需要往右边二分，二分的区间是[mid+1,right]
- 上面分别是往左和往右二分的情况，现在我们需要终止二分的条件，思考极端情况，当数组元素只有一个的时候，那么这个元素一定是峰值，所以我们可以得出，当二分的left和right相等的时候，此时直接返回left即可，这个元素一定是峰值
观察1，2两个步骤，可能会有疑问，如果往左或者往右二分的时候，峰值不存在怎么办？回到这篇文章的1D finding推论，当多次二分达到边界之后，此时边界一定会是峰值，所以这样二分是正确的
由此可以写出代码
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length, i = 0, j = n - 1;
while (i < j) {
int m = i + j >> 1;
if (nums[m] > nums[m + 1]) {
j = m;
} else {
i = m + 1;
}
}
return i;
}
}74. 搜索二维矩阵
方法1 暴力
首先暴力法很容易想到，时间复杂度$O(MN)$
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == target)
return true;
}
}
return false;
}
}方法2 二分
一个二维矩阵，总是可以展开成一维数组来存储，满足题目中条件的矩阵展开成一维数组后就是一个升序序列，求一个升序序列中是否存在目标值，当然可以用二分法来做，明确可以用二分之后，也有很多种做法，这里先写用整个矩阵来二分
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int r = matrix.length, c = matrix[0].length, size = r * c, i = 0, j = size - 1;
while (i < j) {
int m = i + j >> 1;
int x = m / c, y = m % c;
if (matrix[x][y] == target) {
return true;
} else if (matrix[x][y] > target) {
j = m - 1;
} else {
i = m + 1;
}
}
int x = i / c, y = i % c;
return target == matrix[x][y];
}
}上面是用整个矩阵做二分，时间复杂度是。
注意到这个矩阵里面，每一行都是一个升序序列，那么我们可以确定target在矩阵中大概位于哪一行，然后再在那个区间判断，这样不需要对整个矩阵做二分了
改进后的二分解法，时间复杂度是$O(m+log(n))$
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int r = matrix.length, c = matrix[0].length, size = r * c;
// 1. 确认target处于哪一行
int ind = 0;
for (ind = 0; ind < r; ind ++ ) {
if (matrix[ind][0] <= target && matrix[ind][c - 1] >= target) break;
}
if (ind == r) return false;
int i = 0, j = c - 1;
int[] nums = matrix[ind];
// 注意边界条件，我们在循环内部判断i == j的情况，外层直接返回false即可
while (i <= j) {
int m = i + j >> 1;
if (target == nums[m]) return true;
else {
if (target > nums[m]) i = m + 1;
else j = m - 1;
}
}
return false;
}
}注意到 矩阵的第一列一定也是一个升序数组，所以我们对第一个遍历过程改成二分
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int ind = findIndex(matrix, target) - 1;
if (ind < 0) return false;
return helper(matrix[ind], target);
}
public int findIndex(int[][] matrix, int target){
int i = 0, j = matrix.length;
while (i < j) {
int m = i + j >> 1;
// 如果起始元素大于target，hi不动，让lo逼近hi
if (matrix[m][0] > target) {
j = m;
} else {
i = m + 1;
}
}
return i;
}
public boolean helper(int A[], int target){
int i = 0, j = A.length - 1;
while (i <= j) {
int m = i + j >> 1;
if (A[m] == target)
return true;
else if (A[m] > target)
j = m - 1;
else
i = m + 1;
}
return false;
}
}写得很复杂，没有原来的方法简洁，但是时间复杂度变为
方法3 利用数组特性
这个数组的特点很明显，要想办法利用一下
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]比如这个数组，我们逆时针旋转90度，以7为出发点，就能得到一颗类似于二叉搜索树的矩阵，那么我们从根节点出发，利用搜索树的特性就能得到答案了
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length, m = matrix[0].length;
int x = 0, y = m - 1;
while (x >= 0 && x < n && y >= 0 && y < m) {
if (matrix[x][y] == target) {
return true;
} else if (matrix[x][y] > target) {
y -= 1;
} else {
x += 1;
}
}
return false;
}
}时间复杂度，上面的解法在《剑指offer》里面也有介绍
总结
上面这三道题就是finding问题，由于数组的特殊性，巧妙的解法都是从
A[M]和A[M-1],A[M+1]的关系来入手的