题目重点：二分服务器值上限，线性贪心判定能否挑出 k 个互不相邻的位置；推导单调性、复杂度与非法 k 边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 位置按输入数组线性排列，不是首尾相邻的环。
- 必须恰好选 k 台；若可选至少 k 台，则任选其中 k 台也满足上限。
- k=0 的最大值无数学定义，训练代码拒绝；k>(n+1)//2 不可能，亦拒绝。
- 服务器值可以为负；二分范围取实际最小/最大值。
解题路线
- 给定阈值 x，只允许选 values[i]≤x 的位置。问题变成判断能否挑至少 k 个不相邻下标。
- 从左到右一旦遇到可选位置就立即选择，并跳过下一位置；在一条线性序列中，这个最早选择不会减少之后可选的数量，可用交换论证把任意最优解的首个选择左移。
- 若阈值 x 可行，则所有更大阈值也可行；对 [min(values),max(values)] 二分最小可行 x。
- 返回找到的 x。若还要输出具体 k 台，在该阈值下重跑贪心，选够 k 后停止。
手动走一遍
[2,3,5,9]、k=2：阈值 3 时能选 2 或 3，但不能两者都选，故不可行；阈值 5 时选下标 0 的 2，再选下标 2 的 5，最大值 5。阈值更高仍可行，二分下界停在 5。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections.abc import Sequence
def minimum_maximum_server_value(values: Sequence[int], k: int) -> int:
"""Choose exactly k nonadjacent positions, minimizing their maximum value."""
n = len(values)
if k < 0 or k > (n + 1) // 2:
raise ValueError("invalid k")
if k == 0:
raise ValueError("maximum of an empty selection is undefined")
def feasible(limit: int) -> bool:
picked = 0
i = 0
while i < n:
if values[i] <= limit:
picked += 1
if picked >= k:
return True
i += 2
else:
i += 1
return False
lo, hi = min(values), max(values)
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
if __name__ == "__main__":
assert minimum_maximum_server_value([2, 3, 5, 9], 2) == 5
复杂度
每次判定 O(n)，二分约 O(log R) 次，R=maxValue−minValue+1，故 O(n log R) 时间和 O(1) 额外空间。若值域巨大但不同值少，可先排序去重候选阈值，代价 O(n log n) 预处理。
易错点与追问
容易失分的边界
- 排序服务器数组后挑最小 k 个会破坏原始相邻关系。
- 贪心选中后忘记跳过下一位置。
- 二分的判定写成‘恰好 k’并在找到 >k 个时误判失败。
- 把环形相邻规则套到线性数组，导致首尾被错误视为冲突。
- 没有处理 n=0、k=0 与 k 过大的接口契约。
继续深挖
- 若服务器排成环，如何分首台选/不选两种情形？
- 若最少间隔为 d>1，贪心跳过长度如何变化？
- 如果最大值相同，如何输出字典序最小的下标集合？
