「每日LeetCode」2020年10月25日

本文最后更新于：2023年3月19日 晚上

Lt845. 数组中的最长山脉

845. 数组中的最长山脉

我们把数组 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

思路

暴力遍历+状态记录（数组）

设置一个 max 储存最大山脉子集长度，一个 temp 存储子集，一个 status 记录上坡还是下坡状态。有以下逻辑：

  1. 当 status===0，即上坡时：
    1. 如果数组内无元素或者当前元素比临时数组最后一个元素来得大，说明可以继续上坡，将元素加入临时数组
    2. 山脉最小长度为 3，所以当临时数组长度大于等于 2，且当前元素比临时数组最后一个元素来得小，说明进入下坡状态，将元素加入临时数组。这里可能已经是数组的最后一个元素，判断是否是，是的话计算一下 max
    3. 其他情况说明山脉不合法，从该元素开始重新计算山脉，将 temp 重新设置，仅包含当前元素
  2. 当 status===1，即下坡时：
    1. 当前元素比临时数组最后一个元素来得小，说明可以继续下坡，将元素加入临时数组。这里可能已经是数组的最后一个元素，判断是否是，是的话计算一下 max
    2. 其他情况说明，下坡状态结束，将状态设为上坡。这里注意，要令–i，从当前元素的上一个元素开始判断。

无数组优化

可以看到，山脉判断仅和临时的最后一个元素有关，所以可以使用一个 pre 和 length 来代替 temp 临时数组，节省空间复杂度

解答

暴力遍历+状态记录（数组）

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
/**
 * @param {number[]} A
 * @return {number}
 */
var longestMountain = function (A) {
  let max = 0;
  let temp = [];
  let status = 0;
  for (let i = 0; i < A.length; i++) {
    if (status === 0) {
      if (!temp.length || A[i] > temp[temp.length - 1]) temp.push(A[i]);
      else if (temp.length >= 2 && A[i] < temp[temp.length - 1]) {
        temp.push(A[i]);
        status = 1;
        if (i === A.length - 1) max = Math.max(temp.length, max);
      } else {
        temp = [A[i]];
      }
    } else {
      if (A[i] < temp[temp.length - 1]) {
        temp.push(A[i]);
        if (i === A.length - 1) max = Math.max(temp.length, max);
      } else {
        max = Math.max(temp.length, max);
        status = 0;
        temp = [A[--i]];
      }
    }
  }

  return max;
};

无数组优化

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
36
37
38
39
/**
 * @param {number[]} A
 * @return {number}
 */
var longestMountain = function (A) {
  let max = 0;
  let status = 0;
  let pre = null;
  let length = 0;
  for (let i = 0; i < A.length; i++) {
    if (status === 0) {
      if (!length || A[i] > pre) {
        pre = A[i];
        length++;
      } else if (length >= 2 && A[i] < pre) {
        pre = A[i];
        length++;
        status = 1;
        if (i === A.length - 1) max = Math.max(length, max);
      } else {
        pre = A[i];
        length = 1;
      }
    } else {
      if (A[i] < pre) {
        pre = A[i];
        length++;
        if (i === A.length - 1) max = Math.max(length, max);
      } else {
        max = Math.max(length, max);
        status = 0;
        pre = A[--i];
        length = 1;
      }
    }
  }

  return max;
};