数组中的最长山脉java实现
程序员文章站
2022-10-03 13:55:01
数组中的最长山脉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 的任意子....
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:
输入:[2,1,4,7,3,2,5]
输出:5
解释:最长的 “山脉” 是 [1,4,7,3,2],长度为 5。
示例 2:
输入:[2,2,2]
输出:0
解释:不含 “山脉”。
class Solution {
public int longestMountain(int[] A) {
int res=0;
for(int i=0;i<A.length;i++){
//依次判断每个节点出发的最长山脉
if(res>A.length-i+1){
return res;
}
res=Math.max(res,func(i,A));
}
return res;
}
public int func(int k,int[] A){
int left=k;
//上升长度
while(left+1<A.length&&A[left]<A[left+1]){
left++;
}
//如果上升长度为0或者到顶则返回0
if(left+1==A.length||left==k){
return 0;
}
int right=left;
//下降长度
while(right+1<A.length&&A[right]>A[right+1]){
right++;
}
//如果下降长度为0则返回0
if(right==left){
return 0;
}
//返回上升加下降长度
return right-k+1;
}
}
本文地址:https://blog.csdn.net/zy854816286/article/details/109274480