每日leetcode

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

题目

给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

提示：

• 3 <= arr.length <= 105

• 0 <= arr[i] <= 106

• 题目数据 保证 arr 是一个山脉数组

思路

1. 二分查找，因为数组是保证区间内是严格增或严格减的，如果大于左边界且大于左边的一个元素就缩左边界，如果大于右边界且大于右边的一个元素就缩右边界。因为int的截断，所以可能left=0，right=1时mid等于0无法向下判断，所以直接看哪个大直接返回对应下标即可。另一侧不会有这个问题，因为left=right时对应的结果就是所求下标，这时已经退出循环了。

代码实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size()-1;
        while(left < right) {
            int mid = left + (right-left) / 2;
            if(mid == 0) return arr[left] >= arr[right] ? left : right;
            if(arr[mid]>arr[left] && arr[mid]>arr[mid-1]) left = mid;
            if(arr[mid]>arr[right] && arr[mid]>arr[mid+1]) right = mid;
        }
        return left;
    }
};

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(1)。

官方题解

• 其实不用特判，也不用和边界判断，直接看山脉走势就好了（又想复杂了）。
• 我去，因为山脉数组的长度至少为3，且保证是山脉数组，所以需要判断的位置必然不包括左右端点，直接从1-arr.size()-2中找即可。
• 这里因为通过ans来返回结果，所以需要让left=right做最后一次更新。
• 复现：

• class Solution {
  public:
      int peakIndexInMountainArray(vector<int>& arr) {
          int left = 1, right = arr.size()-2, ans;
          while(left <= right) {
              int mid = left + (right-left) / 2;
              if(arr[mid] > arr[mid+1]) {
                  right = mid - 1;
                  ans = mid;
              }
              else left = mid + 1;
          }
          return ans;
      }
  };