题目描述
给定一个数组 nums，如果数组满足 nums[i] < nums[i + 1] < nums[i + 2] < … < nums[i + k]，并且满足 nums[i + k] > nums[i + k + 1] > … > nums[i + k + n]，则 nums[i] 至 nums[k + n] 为山型数列。
求数组中山型数列的最大长度。
示例：
输入：nums[2, 5, 2, 1, 5]
输出：4
解释：最长山型数列为 [2, 5, 2, 1]
思路
必须满足先递增，然后递减的规则。使用两个指针 head 和 tail，保持 head = tail + 1，比较 nums[head] 和 nums[tail] 的大小关系。同时再加一个 dirFlag 标识当前应该是递增还是递减。⚠️ 只有递减的时候发现 nums[head] >= nums[tail] 的时候才用当前长度更新全局最大长度的值。
实现
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
| public static int maxLength(int[] nums) {
if (nums.length < 3) {
return 0;
}
int length = nums.length;
int maxLength = 0;
for (int i = 0; i < length - 1; i++) {
int dirFlag = 0;
int slow = i;
int fast = i + 1;
int tempLength = 0;
while (fast < length) {
if (dirFlag == 0) {
if (nums[slow] < nums[fast]) {
tempLength++;
slow++;
fast++;
} else {
if (tempLength > 0) {
tempLength++;
dirFlag = 1;
} else {
break;
}
}
} else {
if (nums[slow] > nums[fast]) {
tempLength++;
maxLength = Math.max(maxLength, tempLength);
slow++;
fast++;
} else {
break;
}
}
}
}
return maxLength;
}
|
优化
这种方式每次都要回溯，效率不是很高。