CTF of Z2BNS
0%

山脉数组的峰顶索引

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

我们把符合下列属性的数组 A 称作山脉：

  • A.length >= 3
  • 存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。

示例1：

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

示例2：

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

提示：

  1. 3 <= A.length <= 10000
  2. 0 <= A[i] <= 10^6
  3. A 是如上定义的山脉
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

山脉数组前半部分是递增的后半部分是递减的，就是要求出中间的那个最大的元素下标。

遍历数组，返回第一个元素值大于下个元素值的元素的下标。

c++代码：(执行用时20ms，击败86.50%，内存消耗11.8M，击败6.80%）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n=arr.size();
        for(int i=0;i<n-1;++i){
            if(arr[i]>arr[i+1]){
                return i;
            }
        }
        //其实根据题目要求输入一定是山脉数组，所以for循环中一定会会返回i，但是对整个程序而言有其它输入（不满足题意）会导致for循环不返回，所以要用下面return语句保证编译通过（保证返回一个整数）。
        return 0;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：线性扫描

思路和算法

从左往右扫描直到山的高度不再增长为止，停止增长点就是峰顶。

Java代码：

1
2
3
4
5
6
7
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int i = 0;
        while (A[i] < A[i+1]) i++;
        return i;
    }
}

复杂度分析

  • 时间复杂度：$O(N)$，其中 N是 A 的长度。
  • 空间复杂度：$O(1)$。

方法二：二分查找

思路和算法

将山脉数组中所有满足 A[i] < A[i+1] 的 i 点标记为 True，不满足的点标记为 False。则一个山脉数组可以标记为：[True, True, True, ..., True, False, False, ..., False]。例如山脉数组 [1, 2, 3, 4, 1] 可以标记为 True, True, True, False。

在山脉数组上使用二分查找，找出满足 A[i] < A[i+1] 的最大 i。更多关于 二分查找 的知识，请访问 Leetcode 探索。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int lo = 0, hi = A.length - 1;
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (A[mi] < A[mi + 1])
                lo = mi + 1;
            else
                hi = mi;
        }
        return lo;
    }
}

复杂度分析

  • 时间复杂度：$O(\log N)$，其中 $N$ 是 A 的长度。
  • 空间复杂度：$O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解提供了线性扫描和二分查找两种思路，线性扫描效率要高一些，二分查找也不失为一种方法。注意有的时候where循环比for循环更合适，注意where循环、for循环乃至do…while循环的使用条件。

------------- THE END! THANKS! -------------