题解 | #金字塔数组#

思路：

题目的主要信息：

对于一个数组，如果呈现先递增后递减的趋势，则称之为金字塔数组
求连续数组num中的最长金字塔子数组长度，不存在输出0

方法一：动态规划
具体做法：
我们可以使用最长递增子序列的动态规划法来做这道题。
准备两个数组，increase[i]表示到i为止的最长递增子序列长度，decrease[i]表示从i开始的最长递减子序列长度，我们遍历数组中每个元素，一旦对于某个元素以其为结尾的递增子序列长度和以其开始的递减子序列长度都大于1（因为只有自己时为1），我们认为这是一个金字塔数组，两边长度相加减1即是这个金字塔数组的长度（因为这个元素本身重复计算）。遍历数组，维护最大值即可得到答案。
图片说明

class Solution {
public:
    int getMaxLength(int n, vector<int>& num) {
        int res = 0; 
        vector<int> increase(n + 1, 0);  //统计截至从头到尾下标i的最长递增子序列
        vector<int> decrease(n + 1, 0); // 统计截至从尾到头下标i的最长递增子序列，即正向递减序列
        increase[1] = 1;
        for(int i = 2; i <= n; i++){
            if(num[i - 2] < num[i - 1])
                increase[i] = increase[i - 1] + 1; //递增累加
            else 
                increase[i] = 1; //否则新开一个递增序列
        }
        decrease[n] = 1;
        for(int i = n - 1; i > 0; i--){
            if(num[i] < num[i - 1])
                decrease[i] = decrease[i + 1] + 1; //递减累加
            else
                decrease[i] = 1; //否则新开一个递减序列
        }
        for(int i = 1; i <= n; i++)  
            if(increase[i] > 1 && decrease[i] > 1) //对于某个数，其前递增序列其后递减序列都大于1
                res = max(res, increase[i] + decrease[i] - 1); 
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，三次单循环遍历
空间复杂度： $O(n)$ ，用于动态规划的两个辅助数组长度都为 $n$

方法二：统计波谷
具体做法：
一个数组排列起来就是一个波形数组，金字塔尖就是波峰，如果我们每次都找波峰的话要需要向两边延申，统计长度不方便。我们不妨考虑每次找波谷，因为两个波谷之间的距离就是金字塔数组的长度。我们可以遍历数组，用一个变量记录上一个波谷的坐标（从0开始），一旦找到下一个波谷，计算二者之间的距离，每次维护最大值即可。
图片说明

class Solution {
public:
    int getMaxLength(int n, vector<int>& num) {
        int res = INT_MIN; 
        int index = 0; //统计波谷
        for(int i = 1; i < n - 1; i++){
            if(num[i - 1] > num[i] && num[i] <= num[i + 1]){ //找到波谷
                res = max(res, i - index + 1);
                index = i; //维护新的波谷
            }
        }
        return res == INT_MIN ? n : res; //单调递增序列我们认为也是金字塔数组
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(1)$ ，常数级空间