给定一个长度为n的数组num,数组开始时呈现递增趋势的,到了某一点之后,数组中的值呈现递减趋势,符合这样先增后减规律的数组定义为金字塔数组,求整个num数组中找出长度最长的金字塔数组,如果金字塔数组不存在,请输出0
4,[1,2,3,1]
4
5,[1,5,3,3,1]
3
1<=n<=1000000,且num数组中的数 0<=num[i]<=1000000。
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; } };
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
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; }
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; } }
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;
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是判断,假如是用例一直递增不递减的情况。