文章目录
- 一、题目
- 1.1 题目描述
- 1.2 示例1
- 1.2 示例2
- 1.3 提供的代码
- 二、如何完成这个算法题?
- 2.1 解题思路
- 解释
- 复杂度
一、题目
1.1 题目描述
给定一个长度为 n
的正整数数组,每个元素表示一座山的高度
。
其中满足以下条件的连续子数组称为山脉
:
- 长度大于等于
3
- 存在下标
i
,满足nums[0] < nums[1] < nums[2] < ... < nums[i]
,nums[i] > nums[i+1] > nums[i+2] ... > nums[i+k]
请你找出最长山脉的长度
数据范围:
-
1 ≤ n ≤ 10^5
, 数组中的元素满足1<=nums[i] ≤ 10^4
1.2 示例1
输入
[2,5,2,1,5]
输出
4
说明
[2,5,2,1]
1.2 示例2
输入
[2,2,2,2,1]
输出
0
说明
没有山脉则输出 0
1.3 提供的代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型ArrayList
* @return int整型
*/
public int longestmountain (ArrayList<Integer> nums) {
// write code here
}
}
二、如何完成这个算法题?
2.1 解题思路
这个题目可以通过遍历数组来解决,寻找满足条件的最长山脉
。
我们需要记录每座山脉的起点
、峰值
和终点
,并计算最大长度
。
思路如下:
-
遍历数组:我们从第二个元素开始遍历,直到倒数第二个元素,因为山脉需要左右两侧各有一个
递增
和递减
部分。 -
寻找峰值:一个元素
nums[i]
是峰值,当它满足nums[i - 1] < nums[i] > nums[i + 1]
。 -
计算山脉长度:
- 从峰值开始
向左扩展
,直到不满足递增
条件,记录左边界
。 - 从峰值开始
向右扩展
,直到不满足递减
条件,记录右边界
。 - 计算山脉长度为
right - left + 1
,并更新最长山脉长度
。
- 从峰值开始
-
处理特殊情况:如果没有找到任何山脉,返回
0
。
代码实现如下:
import java.util.ArrayList;
public class Solution {
public int longestmountain(ArrayList<Integer> nums) {
int n = nums.size();
if (n < 3) return 0; // 至少需要三个元素形成山脉
int maxLength = 0;
for (int i = 1; i < n - 1; i++) {
// 判断是否为山峰
if (nums.get(i - 1) < nums.get(i) && nums.get(i) > nums.get(i + 1)) {
int left = i - 1;
int right = i + 1;
// 向左扩展
while (left > 0 && nums.get(left - 1) < nums.get(left)) {
left--;
}
// 向右扩展
while (right < n - 1 && nums.get(right + 1) < nums.get(right)) {
right++;
}
// 计算当前山脉长度
int currentLength = right - left + 1;
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}
}
解释
-
maxLength
记录最长山脉的长度。 - 每当找到一个满足条件的山峰时,向左右扩展以计算山脉的实际长度。
- 最后返回最大山脉的长度。
复杂度
- 时间复杂度:O(n),因为我们在遍历数组时只对每个元素做有限次数的比较和扩展。
- 空间复杂度:O(1),仅使用了固定的额外空间。