【Day 32 】2021-06-10 - 796. Minimum Light Radius

题目描述

796. Minimum Light Radius

入选理由

暂无

题目地址

https://binarysearch.com/problems/Minimum-Light-Radius

前置知识

• 排序

• 二分法

题目描述

You are given a list of integers nums representing coordinates of houses on a 1-dimensional line. You have 3 street lights that you can put anywhere on the coordinate line and a light at coordinate x lights up houses in [x - r, x + r], inclusive. Return the smallest r required such that we can place the 3 lights and all the houses are lit up.

 Constraints

 n ≤ 100,000 where n is the length of nums
Example 1
 Input
nums = [3, 4, 5, 6]
Output
0.5
Explanation
If we place the lamps on 3.5, 4.5 and 5.5 then with r = 0.5 we can light up all 4 houses.

解法一

时空复杂度

时间复杂度：O(logN)

空间复杂度: O(n)

参考回答