首页 > 试题广场 >

金字塔数组

[编程题]金字塔数组
  • 热度指数:1232 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为n的数组num,数组开始时呈现递增趋势的,到了某一点之后,数组中的值呈现递减趋势,符合这样先增后减规律的数组定义为金字塔数组,求整个num数组中找出长度最长的金字塔数组,如果金字塔数组不存在,请输出0

示例1

输入

4,[1,2,3,1]

输出

4
示例2

输入

5,[1,5,3,3,1]

输出

3

备注:
1<=n<=1000000,且num数组中的数 0<=num[i]<=1000000。
思路是找最低点,每次更新max值。
一个判断状态找了一晚上,最后发现是max值更新有问题,应该是right-left+1。还有题目没说清楚连续的相同值算不算到一个波的长度里。根据用例来看是不算的。
class Solution {
public:
    int getMaxLength(int n, vector<int>& num) {
        int max = 0;
        int left=-1,right=-1;
        int temp=-1;
        for(int index=0;index<n;index++)
        {
            if(index==0&&num[1]>=num[0])
            {
                right = 0;
                temp = 0;
                left = 0;
            }
            if(index+1<n&&index-1>=0)
            {
                if(num[index]<=num[index-1]&&num[index]<=num[index+1])   //判断谷底
                {
                    right = index;       //右侧为最新探测到的谷底
                    left = temp;           //左侧为上次探测到的谷底
                    temp = right;
                    if(right>=0&&left>=0)
                        if(right-left+1>max)
                        {
                            max = right - left + 1;
                        }
                }
            }
            if(index==n-1&&num[n-2]>num[n-1])
            {
                right = index;
                left = temp;
                if(right>=0&&left>=0)
                    if(right-left+1>max)
                    {
                        max = right - left + 1;
                    }
            }
        }
        if(left>=0&&right>=0)
        {
            return max;
        }
        return 0;
    }
};


发表于 2020-07-23 02:02:24 回复(0)
思路是: 上坡查找(最小值) 下坡查找(最大值) 上坡查找: 根据最小值分左右两侧,左侧上坡长度,右侧上坡长度,相等记录判断是否满足数组最大坡长num.length/2满足返回,不相等舍弃。 计算当前最小值左侧最小值和右侧最小值重复以上计算。从记录中取最大值,无值返回0。 两侧下标为终止递归条件。
发表于 2020-08-30 11:24:35 回复(0)
不多说,直接上代码,看注释 ,哈哈
class Solution:
    def getMaxLength(self , n , num ):
        if len(num)<1:
            return 0
        #储存波谷点的数组
        res=[]
        # 寻找所有的波谷点
        if(num[1]>=num[0]):
            res.append(0)
            
        for i in range(1,n-1):
            if num[i-1]>=num[i] and num[i]<=num[i+1]:
                res.append(i)
                
        if num[n-2]>=num[n-1]:
            res.append(n-1)
        # 将相邻两个波谷点的最大值结果保存在result中
        result=0
        for i in range(1,len(res)):
            result=max(result,res[i]-res[i-1]+1)
            
        return result

发表于 2020-08-04 23:11:17 回复(0)
    public int getMaxLength (int n, int[] num) {
        if(num==null||num.length==0) {
            return 0;
        }
        int minIndex=0;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < n-1; i++) {
            if(num[i-1]>num[i]&&num[i]<=num[i+1]) {
                max = Math.max(max,i-minIndex+1);
                minIndex=i;
            }
        }
        return max==Integer.MIN_VALUE?n:max;
    }

发表于 2020-08-02 23:07:43 回复(0)
 
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param num int整型一维数组 
     * @return int整型
     */
    public int getMaxLength (int n, int[] num) {
        // write code here
        //lefti为第i个数左边递减,righti右边递减
        //lefti=lefti-1+1;
        //righti=right(i+1)+1;
        Scanner sc =new Scanner(System.in);
        int len=num.length;
        int []left=new int[len];
        int []right=new int[len];
       
        int max=0;
        left[0]=0;
        right[len-1]=0;
        for(int i=1;i<num.length;i++){
            if(num[i]>num[i-1]){
                left[i]=left[i-1]+1;
            }else{
                left[i]=0;
            }
           
            
        }
        
        for(int i=len-1;i>0;i--){
          if(num[i]<num[i-1]){
                right[i-1]=right[i]+1;
            }else{
                right[i-1]=0;
            }
       }
       for(int i=1;i<num.length;i++){
           if(left[i]+right[i]>0&&left[i]+right[i]+1>max)
           max=left[i]+right[i]+1;
       }
        return max;
        
    }
}

发表于 2020-07-25 16:40:11 回复(0)
 这道题的思路,并没有找波谷点。而是直接将所有的波峰找出来,只要将波峰左侧所有递减和右侧递增的个数求和,就能得到一组金字塔数组长度。进行比较求最大长度即可。这种思路优点比较清晰,结构简单,不容易混淆。缺点是时间复杂度增加。
public int getMaxLength (int n, int[] num) {
        // write code here
        int max=0;
        for(int i=1;i<num.length-1;i++) {
            if(num[i]>num[i-1]&&num[i]>num[i+1]) {
                int len=getLength(i,num);
                max=max>len?max:len;
            }
        
        }
        return max;
    }
   
    private int getLength (int index,int[] num){
        int len=1;
        for(int i=index;i>0;i--) {
            if(num[i]>num[i-1]) len++;
            else break;
        }
        for(int i=index;i<num.length-1;i++) {
            if(num[i]>num[i+1]) len++;
            else break;
        }
        return len;
    }
发表于 2020-07-20 11:57:38 回复(0)
可以将其想象成波的样子,题目则是求最长的波长,我们只用找到所有波谷点的index,然后相邻点index逐一相减,取最大差值则得题解。波谷点的特点则是上一个点比它大,下一个点也比他大,但考虑到相邻点可能相等的情况,这里波谷点判断得加上相等。代码如下。
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param num int整型一维数组 
     * @return int整型
     */
    public int getMaxLength (int n, int[] num) {
        List<Integer> troughs = new ArrayList();
        if (num[1] >= num[0]) troughs.add(0);
        for (int i = 1; i < num.length - 1; i++) {
            if (num[i-1] >= num[i] && num[i] <= num[i+1]) {
                troughs.add(i);
            }
        }
        if (num[num.length-2] >= num[num.length-1]) troughs.add(num.length-1);
        int result = 0;
        for (int i = 1; i < troughs.size(); i++) {
            int length = troughs.get(i) - troughs.get(i-1);
            result = Math.max(result,length);
        }
        return result + 1;
  

发表于 2020-07-15 15:59:22 回复(1)
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param num int整型一维数组 
     * @return int整型
     */
    public int getMaxLength (int n, int[] num) {
        // write code here
        int max = 0;
        int now = 1;
        int cur = 0;
        int flag = 1;
        for(int i =1;i<n;i++){
            cur = num[i];
            if(num[i-1]<cur){
                if(flag==0){
                    max = Math.max(max,now);
                    flag = 1;
                    now = 1;
                }
                now++;
            }else if(num[i-1]>cur){
                now++;
                flag = 0;
            }else{
                max = Math.max(max,now);
            }
        }
        return max==0?now:max;
    }
}
简单粗暴nt解法。最后max==0是判断,假如是用例一直递增不递减的情况。
发表于 2020-07-15 10:40:54 回复(0)