475. 供暖器 - 力扣（LeetCode） (leetcode-cn.com)

難度：中等
題目描述：冬季已經(jīng)來(lái)臨。 你的任務(wù)是設(shè)計(jì)一個(gè)有固定加熱半徑的供暖器向所有房屋供暖。
在加熱器的加熱半徑范圍內(nèi)的每個(gè)房屋都可以獲得供暖。
現(xiàn)在，給出位于一條水平線上的房屋 houses 和供暖器 heaters 的位置，請(qǐng)你找出并返回可以覆蓋所有房屋的最小加熱半徑。
說(shuō)明：所有供暖器都遵循你的半徑標(biāo)準(zhǔn)，加熱的半徑也一樣。

分析

排序+雙指針 
此題使用雙指針，為每一個(gè)房子位置尋找最近供熱器位置，再將最大值找出，即為全局最小半徑距離 
使用雙指針的前提就是兩個(gè)數(shù)組是有序的，
 所以需要對(duì)兩個(gè)數(shù)組排序，此時(shí)時(shí)間復(fù)雜度：O(mlogm+nlogn)。 
對(duì)于有序數(shù)組來(lái)說(shuō)，只需要設(shè)置一個(gè)指針指向houses數(shù)組，一個(gè)指針指向heaters數(shù)組即可

解題

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
            Arrays.sort(heaters);

            int m = houses.length;
            int n = heaters.length;
            int result = 0;
            for (int i = 0, j = 0; i < m; i++) {
                int curr = Math.abs(houses[i] - heaters[j]);
                while (j < n-1 && Math.abs(houses[i] - heaters[j+1]) <= curr){
                    j++;
                    curr = Math.min(curr, Math.abs(houses[i] - heaters[j]) );
                }
                result = Math.max(curr, result);
            }
            return result;
    }
}