2026-10-28：栅栏的最宽宽度。用go语言，有一个整数序列 planks，第 i 个元素代表第 i 块原始木板的高度。每块原始木板的宽度都是 1。 现

2026-10-28：栅栏的最宽宽度。用go语言，有一个整数序列 planks，第 i 个元素代表第 i 块原始木板的高度。每块原始木板的宽度都是 1。

现在要用这些木板组成一段栅栏。栅栏中所有最终使用的木板必须高度一致。每块原始木板有两种处理方式：一是单独作为一块木板使用；二是与另一块不同的原始木板拼接，拼接后的木板高度等于两块原始木板高度之和。每块原始木板最多只能参与一次，也可以选择不使用某些原始木板。拼接得到的木板仍按一块宽度为 1 的木板计算。

要求在所有可行方案中，找出能够使栅栏达到的最大宽度。

1 <= planks.length <= 1000。

1 <= planks[i] <= 1000000000。

输入： planks = [1,3,2,5,7,5,4,2,1]。

输出： 4。

解释：

我们可以得到四块高度为 5 的木板。

planks[3] = 5

planks[5] = 5

planks[0] + planks[6] = 1 + 4 = 5

planks[1] + planks[2] = 3 + 2 = 5

因此，最大宽度为 4。

题目来自离开4007。

大体步骤如下： 第一步：统计每种原始木板高度出现的次数

先遍历一遍planks，用一个映射记录：

• • 高度x出现了多少次，记为cnt[x]。

例如题目例子中：

• • 高度 1 出现 2 次；

• • 高度 2 出现 2 次；

• • 高度 3 出现 1 次；

• • 高度 4 出现 1 次；

• • 高度 5 出现 2 次；

• • 高度 7 出现 1 次。

这一步的目的是后续按“高度类别”批量计算，而不是一块一块木板去尝试。

第二步：准备一个“目标高度 -> 可得到宽度”的统计表

代码中使用了cntPair这个映射，它的含义是：

对于某个目标栅栏高度 H，目前能够组成多少块高度为 H 的木板。

后面会枚举所有可能的拼接方式，把对应的宽度贡献累加到目标高度上。

第三步：枚举每一种原始高度

对于每一个出现过的不同高度x，设它出现了c = cnt[x]次。代码分别考虑三种贡献。

3.1 高度为的木板单独使用

如果目标栅栏高度就是x，那么所有高度为x的原始木板都可以直接单独作为一块木板使用。

因此，对于目标高度x，可以直接贡献c块宽度为 1 的木板。

也就是说，目标高度x的可用宽度至少增加c。

3.2 两块高度都为的木板拼接成高度2x

两块高度都为x的原始木板可以拼成一块高度为2x的木板。

同一高度x一共有c块，每两块配成一对，所以最多可以配出：

c / 2

对，也就是向下取整。

因此，对于目标高度2x，可以增加c / 2块木板。

这里用整数除法，保证不会多使用木板。例如有 5 块高度为x的木板，只能拼出 2 块高度为2x的木板，剩下 1 块不能和同一块自己拼接。

3.3 高度为的木板与更高的高度y拼接

代码再枚举另一个不同高度y，并且只处理：

y > x

这样可以保证每一对高度(x, y)只被处理一次，避免把x+y和y+x重复统计。

对于高度x和高度y：

• • 高度x有cnt[x]块；

• • 高度y有cnt[y]块；

• • 每一块高度为x的木板可以和一块高度为y的木板拼接；

• • 拼接后的高度是x + y；

• • 最多能配出的数量是：

min(cnt[x], cnt[y])

因此，对于目标高度x + y，可以增加：

min(cnt[x], cnt[y])

块木板。

这里取最小值是因为两类木板数量可能不一样，配对数量受较少的一类限制。每一块原始木板最多参与一次，因此不能超过任意一类的数量。

第四步：为什么这些贡献可以相加

对于某个固定目标高度H，可能有多种来源：

1. 1. 高度正好为H的木板单独使用；

2. 2. 两个较小高度a + b = H拼接；

3. 3. 两个相同高度x + x = H拼接，也就是H = 2x。

这些来源使用的原始木板高度集合是不同的：

• • 单独使用高度H的木板，不会用到高度小于H的木板；

• • 拼接成H的高度对(a, b)中，a和b都小于H；

• • 同高度拼接x + x = H中，x = H / 2，代码单独用c / 2处理，避免和不同高度对重复；

• • 不同的高度对(x, y)使用的木板高度不同，不会争用同一类原始木板。

所以对于同一个目标高度，不同来源的宽度可以直接累加。

另外，最终只需要选择一个目标高度作为栅栏高度，因此不同目标高度之间是互相独立的。代码对每个可能的目标高度分别计算理论最大宽度，最后取最大值即可。

第五步：遍历所有目标高度，取最大宽度

在完成上面的枚举后，cntPair中记录了若干个“目标高度”对应的可用木板数量。

最后遍历cntPair的所有值，取其中最大的一个，就是能够形成的栅栏最大宽度。

对于题目例子：

planks = [1,3,2,5,7,5,4,2,1]

考虑目标高度 5：

• • 单独使用高度 5 的木板有 2 块；

• •1 + 4 = 5，可以配 1 对；

• •3 + 2 = 5，可以配 1 对；

总共得到：

2 + 1 + 1 = 4

因此最大宽度为 4。

时间复杂度

设：

• •n = len(planks)；

• •m为不同高度的个数，m <= n。

各部分复杂度：

1. 1. 统计每种高度出现次数：遍历一次数组，时间复杂度O(n)。

2. 2. 枚举不同高度x：外层遍历m种高度。

3. 3. 对每个x，再遍历所有不同高度y，内层也是O(m)。

4. 4. 因此两层枚举高度对的总复杂度是O(m^2)。

5. 5. 最后遍历cntPair取最大值。cntPair中键的数量最多为：

   数量上界是O(m^2)，所以最后遍历也是O(m^2)。

• • 每个高度单独贡献一个键；

• • 每个高度翻倍贡献一个键；

• • 每对不同高度贡献一个和；

因此总时间复杂度为：

O(n + m^2) = O(n^2)

最坏情况下m = n，所以是O(n^2)。

额外空间复杂度

额外空间主要来自两个映射：

1. 1.cnt记录每种高度出现次数，最多m个键，空间O(m)。

2. 2.cntPair记录每个可能目标高度对应的宽度，键的数量最多为O(m^2)，空间O(m^2)。

因此总额外空间复杂度为：

O(m + m^2) = O(m^2)

最坏情况下m = n，所以额外空间复杂度为：

O(n^2)

• • 总时间复杂度：O(n^2)，最坏情况下等价于O(m^2)。

• • 总额外空间复杂度：O(n^2)，最坏情况下等价于O(m^2)。

其中n是planks的长度，m是不同木板高度的数量。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func maximumWidth(planks []int) (ans int) {
    // 统计 planks 的元素出现次数
    cnt := map[int]int{}
    for _, x := range planks {
        cnt[x]++
    }

     // 枚举所有高度对 (x,y)
    cntPair := map[int]int{}
    for x, c := range cnt {
        cntPair[x] += c       // 方便最后算 max
        cntPair[x*2] += c / 2// 高为 x 的木板内部配对
        for y, c2 := range cnt {
            if y > x { // 避免 x+y 和 y+x 重复统计
                cntPair[x+y] += min(c, c2)
            }
        }
    }

     // 枚举栅栏高度
    for _, c := range cntPair {
        ans = max(ans, c)
    }
    return
}

 func main() {
    planks := []int{1, 3, 2, 5, 7, 5, 4, 2, 1}
    result := maximumWidth(planks)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def maximum_width(planks):
    # 统计每个高度出现的次数
    cnt = {}
    for x in planks:
        cnt[x] = cnt.get(x, 0) + 1

     # cnt_pair[h] 表示最终形成高度 h 的木板最多有多少块
    cnt_pair = {}

     # 枚举所有高度对
    for x, c in cnt.items():
        cnt_pair[x] = cnt_pair.get(x, 0) + c          # 单独使用高度为 x 的木板
        cnt_pair[x * 2] = cnt_pair.get(x * 2, 0) + c // 2  # 两块高度都为 x 的木板配对

         for y, c2 in cnt.items():
            if y > x:  # 避免 x+y 和 y+x 重复统计
                cnt_pair[x + y] = cnt_pair.get(x + y, 0) + min(c, c2)

     ans = 0
    for c in cnt_pair.values():
        ans = max(ans, c)

     return ans

 if __name__ == "__main__":
    planks = [1, 3, 2, 5, 7, 5, 4, 2, 1]
    result = maximum_width(planks)
    print(result)

C++完整代码如下：

  

  

  

  

using namespace std;

 int maximumWidth(const vector& planks) {
    // 统计每个高度出现的次数
    unordered_map cnt;
    for (int x : planks) {
        cnt[x]++;
    }

     // cntPair[h] 表示最终形成高度 h 的木板最多有多少块
    unordered_map cntPair;

     // 枚举所有高度对
    for (auto& [x, c] : cnt) {
        cntPair[x] += c;          // 单独使用高度为 x 的木板
        cntPair[x * 2] += c / 2;  // 两块高度都为 x 的木板配对

         for (auto& [y, c2] : cnt) {
            if (y > x) {          // 避免 x+y 和 y+x 重复统计
                cntPair[x + y] += min(c, c2);
            }
        }
    }

     int ans = 0;
    for (auto& [h, c] : cntPair) {
        ans = max(ans, c);
    }
    return ans;
}

 int main() {
    vector planks = {1, 3, 2, 5, 7, 5, 4, 2, 1};
    int result = maximumWidth(planks);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。