LeetCode845-数组中的最长山脉

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-mountain-in-array/

中文链接：https://leetcode-cn.com/problems/longest-mountain-in-array/

题目详述

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

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

（注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1：

1
2
3
输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

示例 2：

1
2
3
输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000

题目详解

  • 遍历数组，模拟山脉的上升过程和下降过程，更新结果。
  • 注意边界条件。
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
31
32
33
34
35
public class LeetCode_00845 {

    public int longestMountain(int[] A) {
        int n = A.length;
        if (n < 3) {
            return 0;
        }
        int res = 0;
        int i = 1;
        while (i < n) {
            if (A[i - 1] >= A[i]) {
                ++i;
                continue;
            }
            // 上升过程
            int s = i - 1;
            while (i < n && A[i - 1] < A[i]) {
                ++i;
            }
            if (i == n) {
                break;
            }
            if (A[i] == A[i - 1]) {
                continue;
            }
            // 下降过程
            while (i < n && A[i - 1] > A[i]) {
                ++i;
            }
            // 山脉为 [s, i - 1]
            res = Math.max(res, i - s);
        }
        return res;
    }
}