# leetcode-475-Heaters

### 题目描述：

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
3. As long as a house is in the heaters' warm radius range, it can be warmed.

Example 1:

```Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.```

Example 2:

```Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.```

### 说明：

1、这道题目给定两个vector，一个存储了房屋的位置，另一个存储了加热器的位置，要求输出加热器的最小半径，使得加热器可以覆盖所有房子。房屋和加热器都是一维水平向量。

2、假设房屋位置和加热器位置如下：（三角形代表房子，圆形代表加热器）

△△△△△△△△△△△△

○             ○         ○

```    int findRadius(vector<int>& houses, vector<int>& heaters)
{
sort(houses.begin(),houses.end());//排序
sort(heaters.begin(),heaters.end());
int s1=houses.size(),s2=heaters.size(),max1=0;//max1用在最后，存储最大数值
vector<int> res(s1,INT_MAX);//初始值为INT_MAX
for(int i=0,h=0;i<s1&&h<s2;)//上限-房子位置
{
if(heaters[h]>=houses[i])
{
res[i]=heaters[h]-houses[i];
i++;
}
else
h++;
}
for(int i=s1-1,h=s2-1;i>=0&&h>=0;)//房子位置-下限，跟原本数值比较，存储小的值
{
if(heaters[h]<houses[i])
{
res[i]=min(houses[i]-heaters[h],res[i]);
i--;
}
else
h--;
}
for(int i=0;i<s1;i++)
{
if(res[i]>max1)
max1=res[i];
}
return max1;
}```

0 条评论

• ### leetcode-189-Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negativ...

• ### JAVA类Integer

今天带来的是Integer，想必大家都不会陌生，下面会大家从属性、内部类、好玩的几个方法入手，来简单解析下Integer这个类。

• ### 【Java面试题系列】：Java基础知识面试题，看这一篇就够了

参加过社招的同学都了解，进入一家公司面试开发岗位时，填写完个人信息后，一般都会让先做一份笔试题，然后公司会根据笔试题的回答结果，确定要不要继续此次面试，如果答的...

• ### 腾讯智造，新一代云数据库CynosDB，“C”位出道！

CynosDB是腾讯云自研的新一代高性能高可用的企业级分布式云数据库。融合了传统数据库、云计算与新硬件的优势，100%兼容开源数据库，百万级QPS的高吞吐，不限...

• ### 780. Reaching Points

stack over flow，原因很简单，如例子[5, 7, 455955547, 420098884]，想想它的递归深度。

• ### 每日一题 剑指offer（替换空格）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化...

• ### 不知道CynosDB为什么叫真正的云原生数据库？腾讯云数据库的产品欧巴今天跟你聊一聊

注：本文摘自2018年11月22日腾讯云数据库CynosDB新品发布会的演讲实录。随着互联网信息的发展，大家也对云这个词汇也不是特别陌生了，作为全球首选的云服务...