议事大厅-【赛码网】..

第一题AC，当时也想过用标志位判断是否为上升或者下降，然后用一个bool判断是不是有过从上升到下降的转换，后面仔细一想，其实只要找出每个谷底的坐标，再判断每两个谷底之间的距离，取一个最大值就有结果了，再考虑一下首尾以及判断一下是否为一个峰（中间至少隔一个数）就可以了。代码如下，只是一个函数…list第一个为起点，第二个为终点。

public static List<Integer> GetIndexes(int array[],int n){

int start=-1,end=-1;

int sum=0;

List<Integer> updown=new ArrayList<Integer>();

if(array[1]>array[0])

updown.add(0);

for(int i=1;i<n-1;i++)

if(array[i]<array[i+1]&&array[i]<array[i-1])

updown.add(i);

if(array[n-1]<array[n-2])

updown.add(n-1);

for(int i=1;i<updown.size();i++){

int dist=updown.get(i)-updown.get(i-1);

if(dist>=3&&dist>sum){

sum=dist;

start=updown.get(i-1);

end=updown.get(i);

}

List<Integer> lst=new ArrayList<Integer>();

lst.add(start);

lst.add(end);

return lst;

}

acmcoder8yH5wPyq

请问dist>=3是为什么呢？中间至少隔一个数的话是不是>=2就好了呀？

2017-03-31 09:01

coder_AJTV4PHH

是不难……就是找出所有比两边都小的位置，从前往后顺序比较间隔距离，首尾特殊判断一下就行了……

2017-03-31 10:38

coder_AJTV4PHH

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int[] arr = new int[n];
    	for(int i = 0; i < n; i++){
    		arr[i] = sc.nextInt();
    	}
    	int left = -1, right = -1;
    	int lastLeft = -1, lastRight = -1;
    	for(int i = 0; i < n-1; i++){
    		if(lastLeft == -1){
    			if(arr[i] < arr[i+1]){
    				lastLeft = i;
    			}
    		}else{
    			if(arr[i] < arr[i+1] && arr[i] < arr[i-1]){
    				lastRight = i;
    				if(lastRight - lastLeft > right - left){
    					left = lastLeft;
        				right = lastRight;
    				}
    				lastLeft = lastRight;
    			}
    		}
    	}
    	if(arr[n-1] < arr[n-2]){
    		lastRight = n-1;
    		if(lastLeft!=-1 && lastRight - lastLeft > right - left){
				left = lastLeft;
				right = lastRight;
			}
    	}
    	System.out.println(left+" "+right);
    }
}

2017-03-31 10:41

coder_UP2BBE5A

思路真好！但是我个人认为dist >= 2也不需要吧，因为在判断是否是谷底的时候已经是和前后两个元素比较过了，两个谷底之间必然会隔一个以上的元素呀，不知道我的想法是否有遗漏的地方，望大神赐教！

2017-03-31 14:22

acmcodervuvF6JJ0

我用的java，就是这个思路......结果超时了，过了60%

2017-03-31 14:44

acmcoderkNrsyfuw

确实不难只有这题ACl

2017-03-31 20:07

咪咪麻麻咪咪麻麻

import java.util.*;

public class Main {

	public static void main(String[] args) {
		/*输入*/
		int n;
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		int [] arr = new  int[n];
                for(int i=0;i<n;i++){
                	arr[i]=sc.nextInt();
                }
                /*定义返回区间和最大区间值*/
                int max = 0;
                int [] ret = new int[2];
                ret[0] = -1;
                ret[1] = -1;
                
                /*求最大区间*/
                int temp1=-1,temp2=-1;
                int i=1;
                if(arr[1]<arr[0]){//上升区间为0
                	while(i<n&&arr[i]<arr[i-1]){
                		i++;
                	}
                	//System.out.printf("hello");
                }
                //System.out.printf("jinru%d\n",i);
                temp1 = i-1;//当前最低点
                int count = 0;
                
                while(i<n-1){
                	if(arr[i-1]>arr[i]){
                		if(arr[i+1]>arr[i]){//找到最低点，保存前一个符合条件区间
                			temp2=i;
                			if(count>max){
                				max = count;
                				ret[0]=temp1;
                				ret[1] = temp2;
                				//System.out.printf("shuchu%d %d %d\n",max,ret[0],ret[1]);
                			}
                			temp1 = i;
                			count = 0;//初始化新区间
                		}
                		else{
                			count++;
                			temp2 = i;
                		}
                	}
                	else{
                		if(arr[i]>arr[i+1]){
                			count++;
                			temp2 = i;
                		}
                		else{
                			count++;
                		}
                	}
                	i++;
                }
                if(arr[n-1]<arr[n-2]){
                	count++;
                	if(count>max){
                		ret[0]=temp1;
        				ret[1] = n-1;
                	}
                }
                
                System.out.printf("%d %d",ret[0],ret[1]);
               
                sc.close();
    }
}

2017-04-02 14:29