LeetCode 面试题 16.11. 跳水板

2026-03-28 HGNULB 约 3 分钟

文章信息 3 个分类 2 个标签

分类

题目描述

✅ 面试题 16.11. 跳水板

题意分析

题目目标：必须恰好使用 k 块木板，每块长度只能是 shorter 或 longer，返回所有可能的跳水板总长度，并按升序排列。
核心约束：木板的排列顺序不影响总长度，真正决定答案的只有长木板用了多少块。
特殊情况：k == 0 表示不能搭出跳水板，应返回空数组；两种木板等长时，不论如何选择都只有一个结果。
朴素瓶颈：枚举每块木板选短还是长会产生 $2^k$ 个序列，其中大量序列只是排列不同、总长度相同。

解法：枚举长木板数量

核心思路

设长木板使用 i 块，那么短木板必然使用 k - i 块，总长度为：
\[L_i=longer\times i+shorter\times(k-i)\]
当 longer > shorter 时，i 从 $0$ 增加到 $k$，相邻答案每次增加 longer - shorter，天然严格递增，不需要哈希去重或额外排序。

解题步骤

若 k == 0，直接返回空数组。

若 shorter == longer，返回唯一长度 shorter * k。

否则枚举长木板数量 i = 0..k，把 longer * i + shorter * (k - i) 写入答案。

例如 shorter = 1、longer = 2、k = 3，长木板分别使用 $0,1,2,3$ 块时，总长度依次为 $3,4,5,6$。

代码实现

// i 表示长木板数量；i 从 0 到 k 时答案自然升序。
class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }
        if (longer == shorter) {
            return new int[] {longer * k};
        }
        int[] answer = new int[k + 1];
        for (int i = 0; i < k + 1; ++i) {
            answer[i] = longer * i + shorter * (k - i);
        }
        return answer;
    }
}

// i 表示长木板数量；i 从 0 到 k 时答案自然升序。
func divingBoard(shorter int, longer int, k int) []int {
    if k == 0 {
        return []int{}
    }
    if longer == shorter {
        return []int{longer * k}
    }
    answer := make([]int, k+1)
    for i := 0; i <= k; i++ {
        answer[i] = longer*i + shorter*(k-i)
    }
    return answer
}

复杂度分析

时间复杂度：$O(k)$；两种木板等长或 k == 0 时为 $O(1)$。由于最多有 $k+1$ 个不同答案，线性时间也是输出下界。

空间复杂度：除返回数组外为 $O(1)$；返回结果占 $O(k)$。

关键点总结

“恰好使用 k 块”把选择压缩成一个变量：长木板数量确定后，短木板数量也随之确定。

不同排列不是不同答案，组合计数能直接消除指数级重复。

在 longer > shorter 的前提下，枚举顺序就是答案升序，无需排序。

面试追问若要求返回方案数，答案是 k + 1；两种木板等长时则只有 $1$ 种长度。

易错点总结

对每块木板回溯二选一：k = 30 时会生成超过十亿条选择序列，但最终至多只有 $31$ 个长度。

k == 0 返回 [0]：题意要求没有木板时返回空数组，不是长度为零的方案。

忽略两种木板等长：如 shorter = longer = 2、k = 3，枚举会重复得到四个 6，正确答案只有 [6]。

循环只到 i < k：会漏掉全部使用长木板的最大长度，枚举范围必须包含 $k$。

相似题目

题目	难度	考察点
343. 整数拆分	中等	拆分后的最优乘积
70. 爬楼梯	简单	顺序影响方案数
322. 零钱兑换	中等	无限制选择与最优化