[数据结构与算法]NC15051_求距离

链接: https://ac.nowcoder.com/acm/problem/15051
来源：牛客网

描述

给你一个1 -> n的排列，现在有一次机会可以交换两个数的位置，求交换后最小值和最大值之间的最大距离是多少？

输入

第一行一个数n
之后一行n个数表示这个排列

输出

输出一行一个数表示答案

样例输入

5
4 5 1 3 2

样例输出

3

说明

把1和2交换后
序列为4 5 2 3 1
最大值5在数组的2位置，最小值1在数组的5位置
距离为3

备注

对于100%的数据，1 <= n <= 100

解题思路

由于是1 -> n的排列，不考虑重复元素对结果的影响，要使距离最大，应该与边界交换，枚举下列情况

• 最大值与最左边交换
• 最大值与最右边交换
• 最小值与最左边交换
• 最小值与最右边交换

比较得到最大的结果即可

AC代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        String[] strs = bf.readLine().split(" ");
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int maxIndex = 0, minIndex = 0;
        for(int i = 0; i < n; ++i) {
            arr[i] = Integer.parseInt(strs[i]);
            if(arr[i] > max) {
                max = arr[i];
                maxIndex = i;
            }
            if(arr[i] < min) {
                min = arr[i];
                minIndex = i;
            }
        }
        int a = Math.max(Math.abs(minIndex - 0), Math.abs(n - 1 - minIndex));
        int b = Math.max(Math.abs(maxIndex - 0), Math.abs(n - 1 - maxIndex));
        System.out.println(Math.max(a, b)); 
	} 
}