算法问题——最大最小问题（最小最大问题）

475. 供暖器（字串覆盖问题）

/**
 * Copyright (C), 2018-2020
 * FileName: 东方财富笔试
 * Author:   xjl
 * Date:     2020/9/1 21:44
 * Description:
 */
package Test_Pricate;

import org.junit.Test;

import java.util.Arrays;

public class 东方财富笔试 {

    @Test
    public void test() {
        int[] houses = {1, 2, 3, 4, 5, 6, 7, 8, 8, 9};
        int[] heaters = {1, 3, 8};

        int res = findRadius2(houses, heaters);
        System.out.println(res);

    }

    int findRadius(int[] houses, int[] heaters) {
        //找到每个房屋位置所需要的最小半径的最大值
        int res = 0;
        int n = heaters.length;
        Arrays.sort(houses);
        for (int house : houses) {
            //二分法找在供暖的到大于house的第一个值
            int left = 0, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (house > heaters[mid]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            int dist1 = (right == 0) ? Integer.MAX_VALUE : Math.abs(house - heaters[right - 1]);
            int dist2 = (right == n) ? Integer.MAX_VALUE : Math.abs(house - heaters[right]);
            res = Math.max(res, Math.min(dist1, dist2));
        }
        return res;
    }

    public int findRadius2(int[] houses, int[] heaters) {
        // 先排序，踩坑了，以为是顺序的。
        Arrays.sort(houses);
        Arrays.sort(heaters);
        //半径
        int res = 0;
        int index = 0;
        for (int i = 0; i < houses.length; i++) {
            // 找到恰好比当前房屋大的加热器 right 一定在 heaters.length
            while (index + 1 < heaters.length && heaters[index] < houses[i]) {
                index++;
            }
            // 特判，否则会出现越界
            if (index == 0) {
                res = Math.max(res, Math.abs(heaters[index] - houses[i]));
            } else {
                res = Math.max(res, Math.min(Math.abs(heaters[index] - houses[i]), Math.abs(houses[i] - heaters[index - 1])));
            }
        }
        return res;
    }

    public int findRadius3(int[] houses, int[] heaters) {
        // 排序
        Arrays.sort(houses);
        Arrays.sort(heaters);

        // 双指针计算最大半径
        int res = 0;
        int i = 0;
        for (int house : houses) {
            for (i = 0; i < heaters.length - 1; i++) {
                if (Math.abs(heaters[i] - house) < Math.abs(heaters[i + 1] - house)) {  // 查找到当前房屋最近的暖器
                    break;
                }
            }
            // 比较 较大半径
            res = Math.max(res, Math.abs(heaters[i] - house));
        }

        return res;
    }
}