前往
大廳
主題

LeetCode - 475. Heaters 解題心得

Not In My Back Yard | 2020-11-26 00:00:01 | 巴幣 2 | 人氣 197

題目連結:


題目意譯:
冬天將至!在競賽中,你第一個工作是設計一個標準加熱器,其有一個固定的加熱保暖半徑,然後使其溫暖著所有的房子。

每間房子都可以被加熱保暖,只要該房子位於加熱器的範圍之中就可以。

給定一條水平線上的房子以及加熱器的位置,回傳加熱器可能的最小半徑之值使所有加熱器可以覆蓋到所有的房子。

注意所有的加熱器將依從著你設定的半徑,所有加熱半徑都是相同的。

限制:
1 ≦ houses.length 、 heaters.length ≦ 3 × 10 ^ 4
1 ≦ houses[i] 、 heaters[i] ≦ 10 ^ 9



範例測資:
範例 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


解題思維:
這題只需要對於每間房子,找到離它最近的兩個加熱器(如果只有一個就直接算距離)看哪個距離小,然後將這些距離取其中最大值即是所求。

將房子以及加熱器按照位置值之大小各自排序好比較好做。不管是要採取二分搜尋法(Binary Search)去找最近的加熱器,還是要像我一樣用兩個指標去維護著目前的房子以及離該房子最近的加熱器,到了下一間房子就更新負責加熱器的那個指標等等之方式。有排序就是比較方便。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作