宫水三叶的刷题日记

V1

2022/11/17阅读:17主题:全栈蓝

【常见题型总结】二分以及为何能二分(二段性的拓展)

题目描述

这是 LeetCode 上的 162. 寻找峰值 ,难度为 中等

Tag : 「二分」

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞

你必须实现时间复杂度为 的算法来解决此问题。

示例 1:

输入:nums = [1,2,3,1]

输出:2

解释:3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输入:nums = [1,2,1,3,5,6,4]

输出:1 或 5 

解释:你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。

提示:

  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

模拟

由于数据范围只有 ,使用线性扫描找峰值的模拟做法也是没有问题。

代码:

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean ok = true;
            if (i - 1 >= 0) {
                if (nums[i - 1] >= nums[i]) ok = false;
            }
            if (i + 1 < n) {
                if (nums[i + 1] >= nums[i]) ok = false;
            }
            if (ok) return i;
        }
        return -1;
    }
}
  • 时间复杂度:
  • 空间复杂度:

二分

题目让我们实现一个 算法,这是对使用「二分」的强烈暗示。

和往常的题目一样,我们应当从是否具有「二段性」来考虑是否可以进行「二分」

不难发现,如果 在确保有解的情况下,我们可以根据当前的分割点 与左右元素的大小关系来指导 或者 的移动。

假设当前分割点 满足关系 的话,一个很简单的想法是 可能为峰值,而 必然不为峰值,于是让 ,从左半部分继续找峰值。

估计不少同学靠这个思路 AC 了,只能说做法对了,分析没对。

上述做法正确的前提有两个:

  1. 对于任意数组而言,一定存在峰值(一定有解);
  2. 二分不会错过峰值。

我们分别证明一下。

证明 :对于任意数组而言,一定存在峰值(一定有解)

根据题意,我们有「数据长度至少为 」、「越过数组两边看做负无穷」和「相邻元素不相等」的起始条件。

我们可以根据数组长度是否为 进行分情况讨论:

  1. 数组长度为 ,由于边界看做负无穷,此时峰值为该唯一元素的下标;

  2. 数组长度大于 ,从最左边的元素 开始出发考虑:

    • 如果 ,那么最左边元素 就是峰值(结合左边界为负无穷);
    • 如果 ,由于已经存在明确的 大小关系,我们将 看做边界, 看做新的最左侧元素,继续往右进行分析:
      • 如果在到达数组最右侧前,出现 ,说明存在峰值位置 (当我们考虑到 ,必然满足 大于前一元素的前提条件,当然前一元素可能是原始左边界);
      • 到达数组最右侧,还没出现 ,说明数组严格递增。此时结合右边界可以看做负无穷,可判定 为峰值。

综上,我们证明了无论何种情况,数组必然存在峰值。

证明 :二分不会错过峰值

其实基于「证明 」,我们很容易就可以推理出「证明 」的正确性。

整理一下由「证明 」得出的推理:如果当前位置大于其左边界或者右边界,那么在当前位置的右边或左边必然存在峰值。

换句话说,对于一个满足 的位置, 的右边一定存在峰值;或对于一个满足 的位置, 的左边一定存在峰值。

因此这里的「二段性」其实是指:在以 为分割点的数组上,根据 的大小关系,可以确定其中一段满足「必然有解」,另外一段不满足「必然有解」(可能有解,可能无解)。

如果不理解为什么「证明 」的正确性可以由「证明 」推导而出的话,可以重点看看「证明 」的第 点的证明。

至此,我们证明了始终选择大于边界一端进行二分,可以确保选择的区间一定存在峰值,并随着二分过程不断逼近峰值位置。

另外,为了照顾还在纠结使用什么“模板”的同学,特意写了两个版本。但其实只要搞清楚我们「二分」什么内容,根本不会存在说用哪种方式才能写过的情况。

代码:

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}
class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if (n == 1return 0;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > nums[mid - 1]) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}
  • 时间复杂度:
  • 空间复杂度:

总结

通过本题,我们可以对「二分」有进一步的认识。

最早在 33. 搜索旋转排序数组 中,我们强调,二分的本质是「二段性」而非「单调性」,而经过本题,我们进一步发现「二段性」还能继续细分,不仅仅只有满足 特性(满足/不满足)的「二段性」可以使用二分,满足 特性(一定满足/不一定满足)也可以二分。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.162 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1