2017京东校招编程题 烽火台

描述：

n 个 烽火台围成一个圈，任意两个烽火台只要中间的烽火台比他们两个都低就能看见彼此，当然相邻的肯定能看见对面，求能看见彼此的对数

输入 

5    // 烽火台的个数

3    2   5    4     1         //烽火台的高地

输出：

7

思路：观察任意两个烽火台是不是有比他们都低的，有则计数加一，注意要考虑两个方向，因为他们围成了圈圈

实现代码

import java.util.Scanner;

public class Main {
	static int count=0;
	public static void main(String args[]) {
		Scanner in=new Scanner(System.in);
		
		while (in.hasNextInt()) {
			
			int n=in.nextInt();
			
			int arr[]=new int[n];
			for (int i = 0; i <n; i++) {
				arr[i]=in.nextInt();
			}
			
			for (int i = 0; i < arr.length-1; i++) {
				for (int j = i+1; j < arr.length; j++) {
					if (f(i, j, arr)) {
						count++;
					}
				}
			}
			
			System.out.println(count);
			count=0;
			
		}
       
       
      
	}

	private static boolean f(int i, int j,int arr[]) {
		// TODO Auto-generated method stub
		if (Math.abs(i-j)==1||Math.abs(i-j)==arr.length-1) {
			
			return true;
		}
		boolean a=true,b=true;
		for (int k = i+1; k < j; k++) {                //从左往右扫面，看两者之间有没有比他们高的
			if ((arr[k]>arr[i]||arr[k]>arr[j])) {
				a= false;
				break;
			}
		}
		
		for (int step = 1; step <arr.length-(j-i); step++) {        //从右往做扫面，看两者之间有没有比他们高的
			if ((arr[(step+j)%arr.length]>arr[i]||arr[(step+j)%arr.length]>arr[j])) {
				b= false;
				break;
			}
		}
		
		return a||b;
	}
}