Keshawn_lu's Blog

Leetcode 845. 数组中的最长山脉

字数统计: 550阅读时长: 2 min
2020/10/27 Share

题目简介:

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

思路:

利用滑动窗口的思路。

首先right只要满足right < A.size() && A[right] > A[right - 1],便一直往右移动。若right一次也没有移动,则让left++, right = left + 1,直接continue即可。

否则再让right往右移动,需要满足的条件为right < A.size() && A[right] < A[right - 1]。若right一次也没有移动,则说明不满足要求,使新的左端点设为left = right即可(若这里right一次也没有移动,说明此时A[right] == A[right - 1],因为前一个while停止循环时,说明A[right] <= A[right - 1],所以使left = right即可)。

两次right移动至少一次时,说明该区间符合要求,用res保存遍历过程中的最大区间长度。然后使新的左端点left = right - 1即可

tip:

  • A.size() < 3时,直接返回0即可。
  • 需要注意while()条件里,边界条件需要写在最前面做限定

代码如下:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
int longestMountain(vector<int>& A) {

if(A.size() < 3)
return 0;

int res = 0;

int left = 0;
int right = 1;

int flag = 0;

while(left < A.size() && right < A.size()){

while(right < A.size() && A[right] > A[right - 1]){

flag = 1;
right++;
}

if(flag == 0){

left++;
right = left + 1;
continue;
}

flag = 0;

while(right < A.size() && A[right] < A[right - 1]){

flag = 1;
right++;
}

if(flag == 0){

left = right;
right = left + 1;
continue;
}

res = max(res, right - left);

left = right - 1;
right = left + 1;

flag = 0;
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: