leetcode-475.供暖器

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

https://leetcode-cn.com/problems/heaters/

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

示例 3：

输入：houses = [1,5], heaters = [2]
输出：3

// 考虑到所有情况的搜索
var findRadius2 = function (houses, heaters) {
  //  1. 取暖器和房子排序
  houses.sort((a, b) => {
    return a - b
  });
  heaters.sort((a, b) => {
    return a - b
  });
  let max = 0
  const minHeater = heaters[0];
  const maxHeater = heaters[heaters.length - 1];

  houses.forEach((house, houseIndex) => {
    let minRadis;
    if (heaters.length === 1) {
      let min = heaters[0];
      minRadis = Math.abs(house - min);
      max = Math.max(max, minRadis)
      return
    }
    if (house <= minHeater) {
      minRadis = minHeater - house
      max = Math.max(max, minRadis)
      return
    }
    if (house >= maxHeater) {
      minRadis = house - maxHeater
      max = Math.max(max, minRadis)
      return
    }
    else {
      // 在两个中间找到最符合的情况
      let midIndex = heaters.findIndex((heater, heaterIndex) => {
        const beyond = heater <= house;
        const below = house <= heaters[heaterIndex + 1];
        return beyond && below
      });
      minRadis = Math.min(house - heaters[midIndex], heaters[midIndex + 1] - house);
    }
    max = Math.max(max, minRadis)
  })
  console.log(max);
  return max
}

var findRadius3 = function (houses, heaters) {
  let ans = 0;
  heaters.sort((a, b) => a - b);
  for (const house of houses) {
    const i = binarySearch(heaters, house);
    const j = i + 1;
    const leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i];
    const rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;
    const curDistance = Math.min(leftDistance, rightDistance);
    ans = Math.max(ans, curDistance);
  }
  return ans;
};

const binarySearch = (nums, target) => {
  let left = 0, right = nums.length - 1;
  if (nums[left] > target) {
    return -1;
  }
  while (left < right) {
    const mid = Math.floor((right - left + 1) / 2) + left;
    if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid;
    }
  }
  return left;
}


var findRadius4 = function (houses, heaters) {
  houses.sort((a, b) => a - b);
  heaters.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 0, j = 0; i < houses.length; i++) {
    let curDistance = Math.abs(houses[i] - heaters[j]);
    while (j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])) {
      j++;
      curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j]));
    }
    ans = Math.max(ans, curDistance);
  }
  return ans;
};

findRadius2([1, 2, 3], [2])
findRadius([1, 5], [2])
findRadius2([1, 2, 3, 4], [1, 4]) //3
findRadius2([1, 5], [10]) //3
findRadius4(
  [474833169, 264817709, 998097157, 817129560],
  [197493099, 404280278, 893351816, 505795335]
)
Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])
findRadius2(
  [282475249, 622650073, 984943658, 144108930, 470211272, 101027544, 457850878, 458777923],
  [823564440, 115438165, 784484492, 74243042, 114807987, 137522503, 441282327, 16531729, 823378840, 143542612])