LeetCode 845. 数组中的最长山脉 JAVA

超、凢脫俗 2022-12-18 03:59 123阅读 0赞

我们把数组 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
    解释：不含 “山脉”。
     
    
    提示：
    
    0 <= A.length <= 10000
    0 <= A[i] <= 10000
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/longest-mountain-in-array
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
1、通过遍历找到所有的山顶；  
2、对每一个山顶的两边进行延展，也就是山脉长度的计算；  
3、对所有山脉选取最长的即可

class Solution {
        
        public int longestMountain(int[] A) {
        
            int res=0;
            boolean mountaintop=false;
            for(int i=0;i<A.length-1;i++){
        
                if(A[i]<A[i+1]){
        
                    while(i+1<A.length&&A[i]<A[i+1]) i++;
                    res=Math.max(res,longMountain(i,A));
                }
            }
            return res;
        }
        public int longMountain(int index,int []A){
        
            int left=0;
            int right=0;
            for(int i=index;i>=1;i--){
        
                if(A[i]>A[i-1]) left++;
                else break;
            }
            for(int i=index;i<A.length-1;i++){
        
                if(A[i]>A[i+1]) right++;
                else break;
            }
            if(left==0||right==0) return 0;
            return left+right+1;
        }
    }