LeetCode 题解工作台
安排邮筒
给你一个房屋数组 houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。 请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。 答案保证在 32 位有符号整数范围以内。 示例 1： 输入： houses = [1,4,8,…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示前 栋房子，安排了 个邮筒时，每栋房子与离它最近的邮筒之间的距离的最小总和。初始时 ，答案即为 。 我们可以枚举第 个邮筒“管辖”的最后一栋房子 ，即 $0 \leq p \leq i-1$，那么第 个邮筒“管辖”的房子就是 ，我们记 表示给房子 安排一个邮筒的最小总和，那么有状态转移方程：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。
答案保证在 32 位有符号整数范围以内。
示例 1：
输入：houses = [1,4,8,10,20], k = 3 输出：5 解释：将邮筒分别安放在位置 3， 9 和 20 处。 每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
示例 2：
输入：houses = [2,3,5,12,18], k = 2 输出：9 解释：将邮筒分别安放在位置 3 和 14 处。 每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
示例 3：
输入：houses = [7,4,6,1], k = 1 输出：8
示例 4：
输入：houses = [3,6,14,10], k = 4 输出：0
提示：
n == houses.length1 <= n <= 1001 <= houses[i] <= 10^41 <= k <= n- 数组
houses中的整数互不相同。
解题思路
方法一：动态规划
我们定义 表示前 栋房子，安排了 个邮筒时，每栋房子与离它最近的邮筒之间的距离的最小总和。初始时 ，答案即为 。
我们可以枚举第 个邮筒“管辖”的最后一栋房子 ，即 ，那么第 个邮筒“管辖”的房子就是 ，我们记 表示给房子 安排一个邮筒的最小总和，那么有状态转移方程：
其中 的计算方法如下：
时间复杂度 ，空间复杂度 。其中 为房子的数量。
class Solution:
def minDistance(self, houses: List[int], k: int) -> int:
houses.sort()
n = len(houses)
g = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
g[i][j] = g[i + 1][j - 1] + houses[j] - houses[i]
f = [[inf] * (k + 1) for _ in range(n)]
for i in range(n):
f[i][1] = g[0][i]
for j in range(2, min(k + 1, i + 2)):
for p in range(i):
f[i][j] = min(f[i][j], f[p][j - 1] + g[p + 1][i])
return f[-1][k]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is roughly O(n^2 * k) due to evaluating each subarray for each number of mailboxes, with space complexity O(n * k) for the DP table. Precomputing subarray costs reduces repeated computation but does not change the quadratic nature for n houses. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Sorting is necessary before applying DP to ensure median calculations minimize distances.
- question_mark
Consider base cases like k=1 or k equal to the number of houses to check your DP setup.
- question_mark
Check whether your DP transitions correctly compute minimum distances over all partitions.
常见陷阱
外企场景- error
Failing to sort the houses array before computing median costs leads to incorrect minimal distances.
- error
Not precomputing subarray costs can cause TLE for larger n due to repeated absolute sum computations.
- error
Misindexing in DP transitions, especially off-by-one errors in partitions, can return incorrect total distances.
进阶变体
外企场景- arrow_right_alt
Minimizing total distance with mailboxes restricted to integer positions only.
- arrow_right_alt
Maximizing the number of houses covered within a distance threshold per mailbox.
- arrow_right_alt
Allocating mailboxes where certain houses are mandatory mailbox locations.