LeetCode 956. 最高的广告牌

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 网易
标签
数组 动态规划 中途相遇

题目描述

✅ 956. 最高的广告牌

image-20260929105410422

image-20260929105410688

题意分析

每根钢筋可以接到左支架、右支架，或不使用，不能同时用于两侧。要求两根支架最终等高，并最大化这个共同高度；无法得到正高度时返回 0。题目限制钢筋总长不超过 5000，适合按高度差建立动态规划。

解法：高度差动态规划

核心思路

[!blue]

处理完一部分钢筋后，用 dp[d] = h 表示两侧高度差为 d 时，较矮侧能达到的最大高度；对应两侧高度就是 h 和 h + d。不必区分左右名称，因为目标只关心它们是否等高。

同一个差值下，较矮侧更高的状态也意味着两侧都同时更高。剩余钢筋完全相同，后续选择产生的差值变化只取决于 d 和新钢筋长度，与原来的 h 无关；对两种状态采用相同选择，原本更高的一种始终更高。因此每个差值只保留最大的 h，不会丢掉最优方案。

对长度为 x 的钢筋，有三个选择。不用它，保留 (d, h)；放到较高侧，两侧变为 h、h + d + x，得到 (d + x, h)；放到较矮侧，两侧变为 h + x、h + d，新差值是 abs(d - x)。

放到较矮侧时还要判断是否反超：x <= d 时，新矮侧为 h + x；x > d 时，原高侧反而成为新矮侧，高度为 h + d。两种情况合并，新矮侧高度就是 h + min(d, x)。每次更新相同差值时仍只保留较大高度。

每根钢筋只枚举旧表，结果写入新表；新表先复制旧表，表示“不用这根”。这样每种旧安排都恰好扩展三种选择，又不会将本根钢筋反复使用。初始只有 (0, 0) 可达，全部处理后 dp[0] 就是两侧相等时的最大高度。

解题步骤

  1. 初始化 dp[0] = 0，表示两根支架都为空。
  2. 处理一根钢筋前，复制 dp 得到 next，保留不使用它的选择。
  3. 遍历旧表的每个 (diff, best)，更新放到高侧的状态 (diff + x, best)。
  4. 再更新放到矮侧的状态 (abs(diff - x), best + min(diff, x))。
  5. 所有旧状态处理完后令 dp = next；最后返回差值 0 对应的高度。

高度为 0 也可能是可达状态，例如所有已用钢筋暂时都在一侧。Java 用缺键默认值 -1，Go 显式检查键是否存在，保证新产生的零高度状态也会写入，留给后续钢筋继续配平。

代码实现

class Solution {
    public int tallestBillboard(int[] rods) {
        // dp[diff] = 高度差为 diff 时，较矮一侧能达到的最大高度。
        Map<Integer, Integer> dp = new HashMap<>();

        dp.put(0, 0);

        for (int x : rods) {
            // 复制一份即「这根不用」的转移，同时避免同一根被重复使用。
            Map<Integer, Integer> next = new HashMap<>(dp);

            for (Map.Entry<Integer, Integer> e : dp.entrySet()) {
                int diff = e.getKey();
                int best = e.getValue();

                // 放到较高的一侧：矮侧不变，差值变大。
                int d1 = diff + x;

                next.put(d1, Math.max(next.getOrDefault(d1, -1), best));

                // 放到较矮的一侧：可能反超，新矮侧高度为 best + min(diff, x)。
                int d2 = Math.abs(diff - x);
                int b2 = best + Math.min(diff, x);

                next.put(d2, Math.max(next.getOrDefault(d2, -1), b2));
            }

            dp = next;
        }

        return dp.getOrDefault(0, 0);
    }
}

func tallestBillboard(rods []int) int {
    // dp[diff] = 高度差为 diff 时，较矮一侧能达到的最大高度。
    dp := map[int]int{0: 0}

    for _, x := range rods {
        // 复制一份即「这根不用」的转移，同时避免同一根被重复使用。
        next := make(map[int]int, len(dp)*2+1)
        for k, v := range dp {
            next[k] = v
        }

        for diff, best := range dp {
            // 放到较高的一侧：矮侧不变，差值变大。
            d1 := diff + x
            // 缺键表示状态不存在，不能与可达的零高度混为一谈。
            if old, ok := next[d1]; !ok || old < best {
                next[d1] = best
            }

            // 放到较矮的一侧：可能反超，新矮侧高度为 best + min(diff, x)。
            d2 := abs(diff - x)
            b2 := best + min(diff, x)
            if old, ok := next[d2]; !ok || old < b2 {
                next[d2] = b2
            }
        }
        dp = next
    }
    return dp[0]
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：期望 $O(nS)$，S 为钢筋总长度，差值状态不超过 S+1。
  • 空间复杂度：$O(S)$，前后两张状态表。

关键点总结

[!green]

  • 高度差决定后续如何配平，较矮侧高度记录当前能保留的收益。
  • 同差值只保留最大的较矮侧高度，因为它同时提高了两侧，不会让未来更差。
  • 放到矮侧可能使两侧身份互换，必须用绝对差和较小增量统一计算。

易错点总结

[!yellow]

  • 只保留正高度状态，会丢掉“一侧已有钢筋、另一侧仍为空”的必要中间状态。
  • 在遍历旧表时直接往旧表加入状态，可能让同一根钢筋被重复使用。
  • 放到矮侧后总把高度增加 x，会在发生反超时算错新的较矮侧。
  • 忘记保留“不使用”分支，会强迫每根钢筋都加入某一侧。
  • 最后只取差值 0 的状态；其他差值即使高度很大，也不是两根等高支架。

相似题目

题目 难度 关联与区别
416. 分割等和子集 中等 同样平衡两组和，但本题允许不用部分钢筋，还要最大化相等的高度。
1049. 最后一块石头的重量 II 中等 同样用两组差值作状态，原题最小化最终差，本题要求差为0并最大化支架高度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2020/44322116
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！