数组中的最长山脉

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，845. Longest Mountain in Array

先看题目描述

Beqhhd.png

大意就是满足一下两个条件的数组 B 就被称为山脉

  • B.length ≥ 3
  • 存在一个 i，0 < i < B.length - 1，且 B[0] < B[1] < … < B[i] > B[i + 1] > … > B[B.length - 1]

给定一个数组 A，让我们返回数组中山脉的最长长度，若不存在山脉，则返回 0

算法和思路

大致思路就是用一个 index 指针来遍历数组，若 A[index] < A[index + 1]，则当前元素在山脉的左半部分，则继续移动 index 指针，当到达当前山脉的顶点，即A[index] > A[index] + 1时，则之后元素在山脉的右半部分，继续移动指针直至到达右山脚，即 A[index] ≦ A[index + 1]时，则当前山脉结束，将当前山脉长度与最长山脉长度比较来维护最长山脉长度，就这样在移动 index 指针的过程中维护最长山脉长度，最后返回 res

注意：当 index 指针移动到当前山脉顶点时，若 A[index + 1] 与 A[index] 相等，则山脉没有右半部分，移动 index 指针来寻找下一个左山脚

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int longestMountain(int[] A) {
        int len = A.length;
        if (len == 0) return 0;
        int res = 0;
        int index = 0;
        while (index < len - 1) {
            int cur = 1;
            while (index < len - 1 && A[index] < A[index + 1]) {
                index++;
                cur++;
            }
            if (cur == 1) {
                index++;
                continue;
            }
            int pre = cur;
            while (index < len - 1 && A[index] > A[index + 1]) {
                index++;
                cur++;
            }
            if (cur == pre) {
                index++;
                continue;
            }
            res = Math.max(cur, res);
        }
        return res;
    }
}