LeetCode 面试题 17.16. 按摩师

约 3 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
数组 动态规划

题目描述

✅ 面试题 17.16. 按摩师

image-20260929010532908

题意分析

预约已经按时间顺序排列，不能接受相邻的两个预约，求能够接受的最大总时长。不能重排预约来改变相邻关系；空列表没有可接项目，结果为零。

解法：前两项滚动 DP 选择不相邻预约

核心思路

[!blue]

处理当前预约时，所有合法方案只有两类：不接它，或接它。不接时，之前的最优安排可以原样保留；接它时，紧挨着的上一项必须不接，只能把当前时长加到再往前一个前缀的最优值上。两类取最大值，就得到包含当前预约范围的最优答案。

递推只依赖最近两个前缀，无需保存整个数组。处理下标 i 之前，cur 是 nums[0..i-1] 范围内的最优总时长，pre 是 nums[0..i-2] 范围内的最优总时长；起步时尚无预约的范围统一记为零。注意它们不是某个单独预约的时长，也不要求最右边那个预约一定被选择。

因此新值为 next = max(cur, pre + num)。第一项代表不接当前预约，第二项代表接当前预约并避开上一项。两种选择都合法，而且已经覆盖全部方案；旧前缀取最优也不会影响当前选择的可行性，所以新值仍然最优。

先算出 next，再令 pre = cur、cur = next，把两个前缀范围同时向后推进。循环结束后，cur 对应整个列表。空列表不会进入循环，单个预约也能直接由同一更新规则处理。

解题步骤

  1. 令 pre = 0、cur = 0，表示开始时的空前缀。
  2. 读取当前预约时长，计算不接与接两种方案的最大值，保存到 next。
  3. 新值保存后再滚动状态：先 pre = cur，再 cur = next。
  4. 全部预约处理完，返回 cur。

代码实现

class Solution {
    public int massage(int[] nums) {
        int pre = 0;
        int cur = 0;

        for (int num : nums) {
            int next = Math.max(cur, pre + num);

            pre = cur;
            cur = next;
        }

        return cur;
    }
}

func massage(nums []int) int {
    pre := 0
    cur := 0

    for _, num := range nums {
        next := max(cur, pre+num)
        pre = cur
        cur = next
    }

    return cur
}

复杂度分析

  • 时间复杂度：$O(n)$，每个预约只比较两个候选值。
  • 空间复杂度：$O(1)$，只保存两个旧状态与一个新状态。

关键点总结

[!green]

  • 按是否接受当前预约分类，接它时只能使用不包含上一项的前缀。
  • pre、cur 表示两个完整前缀的最优值，不是最近两项的原始时长。
  • 先计算新值，再滚动变量，保持每轮状态含义一致。

易错点总结

[!yellow]

  • 先覆盖 pre 再求 next，可能把上一项已经被选中的方案与当前项相加。
  • 把预约按时长排序，会改变原来的相邻限制。
  • 只比较相邻两个预约并选择较长者，不能代表整个前缀的最优组合。

相似题目

题目 难度 关联与区别
213. 打家劫舍 II 中等 同样选择不相邻项，原题首尾也相邻，需要拆成两个线性区间。
337. 打家劫舍 III 中等 把线性相邻限制扩展为树上父子不能同时选择，状态仍是选与不选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/47994041
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！