题解 | #金字塔数组#
金字塔数组
http://www.nowcoder.com/practice/c45c060453324a0aa2745c62a2bd1a27
金字塔数组
描述
给定一个长度为n的数组num，数组开始时呈现递增趋势的，到了某一点之后，数组中的值呈现递减趋势，符合这样先增后减规律的数组定义为金字塔数组，求整个num数组中找出长度最长的金字塔数组，如果金字塔数组不存在，请输出0
示例
输入：4,[1,2,3,1]
返回：4
示例
输入：5,[1,5,3,3,1]
返回：3
方法二
思路分析
本题我一开始想到了接雨水问题，接雨水问题是根据每一位置左右两侧的最高点计算该位置可以承受的雨水，根据金字塔数组的定义：数组开始时呈现递增趋势的，到了某一点之后，数组中的值呈现递减趋势，符合这样先增后减规律的数组，因此在计算金字塔数组的长度，也就是说找到一条曲线（将数组抽象为一条曲线）的所有波谷（每一子序列的最小值），根据波谷即可计算当前金字塔数组的长度。需要注意的是一开始的位置和最后的位置也可能就是波谷，因此需要单独对这两个位置判断，具体过程如下：
- 如果num[1]>=num[0]，那么开始位置为波谷，进行记录
- 在中间位置上，如果num[i]<=num[i-1]&num[i]<=num[i+1]，那么记录i为波谷
- 结束位置，如果num[n-1]<=num[n-2]，那么记录结束位置为波谷
- 最后将波谷之间的长度进行计算，找到最长的金字塔数组长度
图解
根据给定数组画出折线图，可以很清楚的找到波谷点，然后得到金字塔数组的长度。
核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int
* @param num intvector
* @return int
*/
int getMaxLength(int n, vector<int>& num) {
// write code here
vector<int> temp;
if(n<1) return 0;
//首先判断第一个位置是否为最低点
if(num[0]<=num[1]) temp.push_back(0);
for(int i=1;i<n-1;i++)
{
if(num[i]<=num[i-1]&&num[i]<=num[i+1])
{
temp.push_back(i);//记录每一个子段最低点
}
}
if(num[n-1]<=num[n-2]) temp.push_back(n-1);//判断最后位置是否为子段最低
int max_length=0;
for(int i=1;i<temp.size();i++)
{
max_length=max(max_length,temp[i]-temp[i-1]+1);//两个相邻低点之间即为所求数组长
}
return max_length;
}
}; 复杂度分析
- 时间复杂度：时间主要是开销在寻找所有符合条件的波谷点，以及计算波谷点之间的长度，因此时间复杂度为$O(n)$
- 空间复杂度：需要设置一个存放波谷点的数组，因此空间复杂度最大为$O(n)$
方法二
思路分析
方法二是对方法一的进一步优化，由于题目只需要输出金字塔数组的长度，因此无需使用额外的数组存***谷位置元素，只需要一个变量记录上一个波谷的位置，再找到当前波谷位置时，即可计算出当前金字塔数组的长度，从而节省内存空间。
核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int
* @param num intvector
* @return int
*/
int getMaxLength(int n, vector<int>& num) {
// write code here
if(n<1) return 0;
int min_index;//记录每一个子段最低点的位置
int max_length=0;
//首先判断第一个位置是否为最低点
if(num[0]<=num[1])
{
min_index=0;
}
for(int i=1;i<n-1;i++)
{
if(num[i]<=num[i-1]&&num[i]<=num[i+1])
{
max_length=max(max_length,i-min_index+1);
min_index=i;//令min_index表示当前波谷的上一波谷位置
}
}
if(num[n-1]<=num[n-2]) //判断最后位置是否为子段最低
{
max_length=max(max_length,n-1-min_index+1);//如果存在最后一个金字塔数组，将其比较
}
return max_length;
}
};
复杂度分析
- 时间复杂度：该方法的时间复杂度与方法一相同，都是$O(n)$，不过只存在一次循环，要小一些
- 空间复杂度：空间复杂度相比于方法一减小了，没有设置专门的数组存***谷位置，设置了一个变量存储距离本次波谷最近的波谷位置，因此总的空间复杂度为$O(1)$
