给大家分享下我的头条3.30笔试第一题我的思路,大佬不要笑
发布于 2017-03-31 11:43 2435 次浏览 2 赞 来自 试题交流  
import java. util.*;
public class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] number = new int[n];
		for(int i = 0 ;i<n;i++){
			number[i] = in.nextInt();
		}
		if(n<3)
			System.out.println(-1+" "+-1);
		else{
			//思路是求出所有可能的断点,即左边为下降,右边为上升的转折点,然后枚举相邻两点的距离
			//最长的即为所求。
			List<Integer> breakpoint = new ArrayList<Integer>();
			if(number[1]>number[0])
				breakpoint.add(0);
			for(int i = 1 ; i<n-1 ; i++){
				if(number[i]<number[i-1]&&number[i]<number[i+1])
					if(!breakpoint.contains(i))
						breakpoint.add(i);
			}
			if(number[n-1]<number[n-2]){
				if(!breakpoint.contains(n-1))
					breakpoint.add(n-1);
			}
			
			int length = Integer.MIN_VALUE;
			int start = 0 , end = 0;
			if(breakpoint.size()>1){
				for(int i = 1 ; i<breakpoint.size(); i++){
					if(breakpoint.get(i)-breakpoint.get(i-1)>length){
						length = breakpoint.get(i)-breakpoint.get(i-1);
						start = breakpoint.get(i-1);
						end = breakpoint.get(i);
					}
				}
				System.out.println(start+" "+end);
			}else{
				System.out.println(-1+" "+-1);
			}
		}
	}
}


4 条回复

你AC了吗?我也这个思路,结果超时,只过了60%

2017-03-31 14:46

我过了百分之90,剩下百分之10不知道为毛不过。

我的思路就是:记录每次up和down的位置,然后与之前作比较。

2017-03-31 20:06
acmcoderilIBYr6d 回复 acmcodervuvF6JJ0

AC了,

2017-04-14 19:17
acmcoderilIBYr6d 回复 Vzc

我之前也那么做的,后来发现太麻烦了,你考虑左右端点没

2017-04-14 19:17
添加回复
回到顶部