题解 | #金字塔数组#

题意整理

给定一个长度为n的数组。
求最长的金字塔数组长度。
金字塔数组是指数组中的元素先递增、后递减。

方法一（枚举所有金字塔）

1.解题思路

先找到金字塔左边界。
然后找到金字塔塔顶。
接着找到金字塔右边界。
计算金字塔数组长度，并且继续迭代，得到最长的金字塔长度。

动图展示：
图片说明

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param num int一维数组 
     * @return int
     */
    public int getMaxLength (int n, int[] num) {
        int i=1;
        int res=0;
        while(i<n){
            //寻找金字塔数组左边界
            while(i<n&&num[i]<=num[i-1]){
                i++;
            }
            int l=i-1;
            //寻找金字塔数组塔顶
            while(i<n&&num[i]>num[i-1]){
                i++;
            }
            //寻找金字塔数组右边界
            while(i<n&&num[i]<num[i-1]){
                i++;
            }
            int r=i-1;
            //求最长长度
            res=Math.max(res,r-l+1);
        }

        return res;
    }
}

3.复杂度分析

时间复杂度：只需要一次线性遍历，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度是 $O(1)$ 。

方法二（统计波谷）

1.解题思路

首先找到所有的波谷位置。
金字塔一定在两个波谷之间，所以只需一一比较相邻波谷间的间距，即可得到最长的金字塔长度。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 
     * @param num int一维数组 
     * @return int
     */
    public int getMaxLength (int n, int[] num) {
        //初始化波谷数组
        int[] arr=new int[n];
        int id=0;
        for(int i=0;i<n;i++){
            //如果首位的元素小于第二位，则首位是波谷
            if(i==0&&num[i]<num[i+1]){
                arr[id++]=i;
            }
            //如果某元素小于等于前一位和后一位，则必是波谷
            if(i>0&&i<n-1&&num[i]<=num[i-1]&&num[i]<=num[i+1]){
                arr[id++]=i;
            }
            //如果末位的元素小于倒数第二位，则末位是波谷
            if(i==n-1&&num[i]<num[i-1]){
                arr[id++]=i;
            }
        }
        int res=0;
        //计算最长金字塔长度
        for(int i=1;i<id;i++){
            res=Math.max(res,arr[i]-arr[i-1]+1);
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：需要两次遍历，都是线性的，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外长度为n的arr数组，所以空间复杂度是 $O(n)$ 。