算法-寻找峰值

今天看算法题，刷到一道解法挺巧妙的题目，题目大致描述是这样的：

给定一个数组nums，寻找峰值元素并返回索引。数组可能有多个峰值，只要返回任何一个峰值索引即可

假设 nums[-1] = nums[n] = -∞

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

要求：时间复杂度为 O(log n)

leetcode-162

思路

这道题不看要求的话，其实一次遍历即可以找出一个峰值，时间复杂度为 O(n) 😂

为什么说这道题的解法有点巧妙呢？

分析一下这道题的意思：

什么是峰值？

我们可以想象我们物理中的波，或者数学中的正余弦函数的图，波峰值的特点是不是中间的值最大，两边的值都比中间的值小，而且是 左边的数是升序排序，右边的数是降序排序。这个特性是不是可以利用一下，虽然是局部的，但是可以考虑有序数组的查找算法，题目要求时间复杂度为 O(log n) ，那有序数组的查找算法中 二分查找法 就是这个时间复杂度。😍

其实 找峰值，即找最值，一般算法中找最值的过程必然是一个搜索边界的过程。

在理解二分查找算法时，有讲过另两个查找最值的搜索边界问题：找左边界、找右边界《算法-二分法查找》

解法

虽然分析出了使用二分法查找能找出来，但是这个查找方式和常规的二分法查找有些不同。常规的二分法只需要确定 mid 的值与 目标值的大小以确定是从 mid 的左边还是右边查找。

找峰值确实通过二分法，先拿到 mid 的值，再将 mid 与左右两边的值进行比较来确定往哪边查找

• left < mid < right : 表示在上坡，因此向右侧查找
• left > mid > right : 表示下坡，因此向左侧查找

既然是二分法的变种，我们先将二分法写出来，再改条件

/// 首先先将常规的 二分法公式写出来，再修改搜索条件
    func finkPeakElement(_ nums: [Int]) -> Int {
        guard nums.count >= 1 else {
            return -1
        }
        var left = 0
        var right = nums.count - 1
        while left <= right {
            var mid = left + (right - left)/2
            if nums[mid] == #target {// 查找到
                return mid
            } else if nums[mid] < #target {// 往右侧搜索
                left = mid + 1
            } else if nums[mid] > #target {// 往左侧搜索
                right mid - 1
            }
        }
        return -1
    }

将条件修改，根据前面分析的，对比 mid 的左右两边的值，因此需要获取 mid + 1 或者 mid -1 的值，那就需要注意mid – 1 和 mid + 1 的越界情况了。

/// 查找峰值并返回索引
    /// 对于所有有效的 i 都有 nums[i] != nums[i + 1]
    /// 首先先将常规的 二分法公式写出来，再修改搜索条件
    /// 因为需要比较 mid + 1 或 mid -1 的值，所以需要考虑越界的情况
    func finkPeakElement(_ nums: [Int]) -> Int {
        guard nums.count >= 1 else {
            return -1
        }
        var left = 0
        var right = nums.count - 1
        while left <= right {
            var mid = left + (right - left)/2
            print("第一次分: (mid)")
            if mid == left && mid == right {// 处理边界条件当nums 只有一个元素时，或者峰值在两端时
                print("找到峰值：(nums[mid]), 索引为：(mid)")
                return mid
            } else if mid == right && nums[mid] > nums[mid - 1] {// 找到右端值
                print("找到右端值为峰值：(nums[mid]), 索引为：(mid)")
                return mid
            } else if mid == left && nums[mid] > nums[mid + 1] {// 找到左端值
                print("找到左端值为峰值：(nums[mid]), 索引为：(mid)")
                return mid
            } else if nums[mid] < nums[mid + 1] {// 往右侧搜索, 上坡: 中间值比右边小
                print("上坡：(mid)")
                left = mid + 1
            } else if nums[mid] < nums[mid - 1] {// 往左侧搜索，下坡：中间值比左边小
                print("下坡：(mid)")
                right = mid - 1
            } else if nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1] {// 查找到：中间值比两边都大
                print("找到峰值：(nums[mid]), 索引为：(mid)")
                return mid
            }
        }
        return -1
    }

上面的 if…else… 有点多，可以单独抽取出来，分三种情况

• left = mid + 1
• right = mid – 1
• return mid

我们可以将 边界条件的 return mid 条件抽取为一个方法

/// 查找峰值并返回索引
    /// 对于所有有效的 i 都有 nums[i] != nums[i + 1]
    /// 首先先将常规的 二分法公式写出来，再修改搜索条件
    /// 因为需要比较 mid + 1 或 mid -1 的值，所以需要考虑越界的情况
    func finkPeakElement(_ nums: [Int]) -> Int {
        guard nums.count >= 1 else {
            return -1
        }
        var left = 0
        var right = nums.count - 1
        while left <= right {
            var mid = left + (right - left)/2
            print("第一次分: (mid)")
            if isPeakElementBounds(nums, mid: mid, left: left, right: right){
                print("边界条件找到峰值：(nums[mid]), 索引为：(mid)")
                return mid
            } else if nums[mid] < nums[mid + 1] {// 往右侧搜索, 上坡: 中间值比右边小
                print("上坡：(mid)")
                left = mid + 1
            } else if nums[mid] < nums[mid - 1] {// 往左侧搜索，下坡：中间值比左边小
                print("下坡：(mid)")
                right = mid - 1
            } else if nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1] {// 4.当峰值在非两端的中间区域时
                print("找到峰值：(nums[mid]), 索引为：(mid)")
                return mid
            }
        }
        return -1
    }
    
    // 是否边界情况
    func isPeakElementBounds(_ nums: [Int], mid: Int, left: Int, right: Int) -> Bool {
        // 1.处理边界条件当nums 只有一个元素时
        // 2.nums.count > 1当峰值在最右端时
        // 3.nums.count > 1当峰值在最左端时
        if mid == left && mid == right {
            return true
        } else if mid == right && nums[mid] > nums[mid - 1] {
            return true
        } else if mid == left && nums[mid] > nums[mid + 1] {
            return true
        } else {
            return false
        }
    }