2022-01-27：供暖器。

冬季已經來臨。 你的任務是設計一個有固定加熱半徑的供暖器向所有房屋供暖。

在加熱器的加熱半徑範圍內的每個房屋都可以獲得供暖。

現在，給出位於一條水平線上的房屋 houses 和供暖器 heaters 的位置，請你找出並返回可以覆蓋所有房屋的最小加熱半徑。

說明：所有供暖器都遵循你的半徑標準，加熱的半徑也一樣。

輸入： houses = ［1，2，3，4］， heaters = ［1，4］

輸出： 1

解釋： 在位置1， 4上有兩個供暖器。我們需要將加熱半徑設為1，這樣所有房屋就都能得到供暖。

力扣475。

答案2022-01-27：

對房子和供暖器排序。

比如地點是7， 9， 14

供暖點的位置： 1 3 4 5 13 15 17

先看地點7

由1供暖，半徑是6

由3供暖，半徑是4

由4供暖，半徑是3

由5供暖，半徑是2

由13供暖，半徑是6

由此可知，地點7應該由供暖點5來供暖，半徑是2

再看地點9

供暖點不回退

由5供暖，半徑是4

由13供暖，半徑是4

由15供暖，半徑是6

由此可知，地點9應該由供暖點13來供暖，半徑是4

為什麼是13而不是5？因為接下來的地點都會更靠右，所以半徑一樣的時候，就應該選更右的供暖點

再看地點14

供暖點不回退

由13供暖，半徑是1

由15供暖，半徑是1

由17供暖，半徑是3

由此可知，地點14應該由供暖點15來供暖，半徑是1

以此類推

時間複雜度：O（N）。

額外空間複雜度：O（1）。

程式碼用golang編寫。程式碼如下：

package mainimport （ “fmt” “sort”）func main（） { houses ：= ［］int{1， 2， 3， 4} heaters ：= ［］int{1， 4} ret ：= findRadius（houses， heaters） fmt。Println（ret）}func findRadius（houses ［］int， heaters ［］int） int { sort。Ints（houses） sort。Ints（heaters） ans ：= 0 // 時間複雜度O（N） // i是地點，j是供暖點 for i， j ：= 0， 0； i < len（houses）； i++ { for ！best（houses， heaters， i， j） { j++ } ans = getMax（ans， abs（heaters［j］-houses［i］）） } return ans}// 這個函式含義：// 當前的地點houses［i］由heaters［j］來供暖是最優的嗎？// 當前的地點houses［i］由heaters［j］來供暖，產生的半徑是a// 當前的地點houses［i］由heaters［j + 1］來供暖，產生的半徑是b// 如果a < b， 說明是最優，供暖不應該跳下一個位置// 如果a >= b， 說明不是最優，應該跳下一個位置func best（houses， heaters ［］int， i， j int） bool { return j == len（heaters）-1 || abs（heaters［j］-houses［i］） < abs（heaters［j+1］-houses［i］）}func abs（a int） int { if a < 0 { return -a } else { return a }}func getMax（a， b int） int { if a > b { return a } else { return b }}

執行結果如下：

***

［左神java程式碼］（https：//github。com/algorithmzuo/coding-for-great-offer/blob/main/src/class47/Problem_0475_Heaters。java）