Leetcode 162. 寻找峰值(Java + 二分)

2023-12-20 07:12:24

题目

  • 162. 寻找峰值
  • 峰值元素是指其值严格大于左右相邻值的元素。
  • 给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
  • 你可以假设 nums[-1] = nums[n] = -∞ 。
  • 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
  • 1 <= nums.length <= 1000
  • -2 ^ 31 <= nums[i] <= 2 ^ 31 - 1
  • 对于所有有效的 i 都有 nums[i] != nums[i + 1]

解法

Java + 二分:

第 1 步:

  • 首先时间复杂度为 O(logn)可以联想到 二分/二叉树 类似的做法,
  • 如果是二分,则需要具备单调性

第 2 步:

  • 我们考虑数组可能出现的情况,抽象出来分为四种:递增、递减、先减后增、先增后减
  • 其他情况都是这四种的组合

第 3 步:

  • 分析四种情况:
    • 递增则最后一个元素一定满足,因为大于前一个元素、且大于 nums[n] = -∞
    • 递减则第一个元素一定满足,因为大于后一个元素、且大于 nums[0] = -∞
    • 先减后增则第一个或者最后一个元素均满足,如上
    • 先增后减则增的那段最后一个元素(也是减的那段第一个元素)满足
  • 可以总结下,递增那段最后一个元素,递减那段第一个元素

第 4 步:

  • 因此模拟二分,
    • 如果 nums[mid] > nums[mid+1] 先判断 mid,不满足则区间左侧满足,
    • 如果 nums[mid] < nums[mid+1] 先判断 mid + 1,不满足则区间右侧满足,
  • 时间复杂度:O(logn),空间复杂度:O(1)

代码

/**
 * Java + 二分:
 *
 * 第 1 步:
 * 首先时间复杂度为 O(logn)可以联想到 二分/二叉树 类似的做法,
 * 如果是二分,则需要具备单调性,
 *
 * 第 2 步:
 * 我们考虑数组可能出现的情况,抽象出来分为四种:递增、递减、先减后增、先增后减
 * 其他情况都是这四种的组合
 *
 * 第 3 步:
 * 分析四种情况:
 *     * 递增则最后一个元素一定满足,因为大于前一个元素、且大于 nums[n] = -∞
 *     * 递减则第一个元素一定满足,因为大于后一个元素、且大于 nums[0] = -∞
 *     * 先减后增则第一个或者最后一个元素均满足,如上
 *     * 先增后减则增的那段最后一个元素(也是减的那段第一个元素)满足
 * 可以总结下,递增那段最后一个元素,递减那段第一个元素
 *
 * 第 4 步:
 * 因此模拟二分,
 *     * 如果 nums[mid] > nums[mid+1] 先判断 mid,不满足则区间左侧满足,
 *     * 如果 nums[mid] < nums[mid+1] 先判断 mid + 1,不满足则区间右侧满足,
 * 时间复杂度:O(logn),空间复杂度:O(1)
 *
 */
public int findPeakElement(int[] nums) {

    int left = 0;
    int right = nums.length - 1;
    int res = left;
    while (left < right) {
        int mid = ((right - left) >> 1) + left;
        if (nums[mid] > nums[mid + 1]) {
            right = mid - 1;

            if (mid == 0 || nums[mid] > nums[mid - 1]) {
                res = mid;
            }

        } else {
            left = mid + 1;

            if (mid + 1 == nums.length - 1 || nums[mid + 1] > nums[mid + 2]) {
                res = mid + 1;
            }
        }
    }

    return res;
}

文章来源:https://blog.csdn.net/qq_33530115/article/details/135074416
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。