LeetCode 补充题 156. 最小周长三角形

2026-09-13 HGNULB 约 4 分钟

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

分类

补充题困难

题目描述

[!green]

牛客原题： ✅ 补充题 156. 最小周长三角形

给定正整数数组 nums，从中选三个不同下标的元素作为三条边，组成非退化三角形，使周长最小。

本题保证有解。返回最小周长，使用 64 位整数累加。

示例 1：

输入： nums = [2,8,4,11,9]
输出： 19
解释： 选择长度 2、8、9，满足 2+8>9，周长为 19；没有周长更小的合法三角形。

提示：

数组元素为正整数，保证可以组成非退化三角形。
三个下标互不相同。
最短两边之和必须严格大于最长边。
返回 64 位周长。

题意分析

排序后选边 a <= b <= c，合法性只需检查 a + b > c。要使周长最小，固定两条较大边后，应选择满足 a > c-b 的最小前缀元素，而不是机械地检查连续三个数。

解法：枚举相邻大边并二分最小边

核心思路

[!blue]

先证明只需枚举相邻的中间边与最大边。若一个最优方案的 b、c 之间还有元素 d，则 b <= d <= c，用 d 替换 c 后，a+b>c 仍保证 a+b>d，周长不会增大。因此总存在两条大边在排序下标上相邻的最优方案。

枚举 b = nums[j]、c = nums[j+1]，在半开区间 [0,j) 二分第一个严格大于 c-b 的值。它是固定这两条边时可用的最小边；若二分返回 j 则没有候选，不能重复使用中间边下标。

将所有合法候选周长取最小即可。相等长度可以来自不同下标，非退化条件必须用严格大于；求差和求和先提升到 64 位，排序会原地改变数组顺序。

解题步骤

先排序，枚举相邻的中间边 b 与最大边 c。

在 b 之前二分第一个大于 c-b 的元素作为最小边。

存在合法最小边时，用 64 位计算周长并更新最小值。

代码实现

class Solution {
    public long minPerimeter(int[] nums) {
        Arrays.sort(nums);
        long answer = Long.MAX_VALUE;

        for (int j = 1; j + 1 < nums.length; j++) {
            long threshold = (long) nums[j + 1] - nums[j];
            int l = 0;
            int r = j;

            while (l < r) {
                int mid = (l + r) >>> 1;

                if (nums[mid] <= threshold) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }

            if (l < j) {
                answer = Math.min(answer, (long) nums[l] + nums[j] + nums[j + 1]);
            }
        }

        return answer == Long.MAX_VALUE ? -1 : answer;
    }
}

import "sort"

func minPerimeter(nums []int) int64 {
    sort.Ints(nums)
    answer := int64(1<<63 - 1)
    for j := 1; j+1 < len(nums); j++ {
        threshold := int64(nums[j+1]) - int64(nums[j])
        l, r := 0, j
        for l < r {
            mid := (l + r) / 2
            if int64(nums[mid]) <= threshold {
                l = mid + 1
            } else {
                r = mid
            }
        }
        if l < j {
            answer = min(answer, int64(nums[l])+int64(nums[j])+int64(nums[j+1]))
        }
    }
    if answer == int64(1<<63-1) {
        return -1
    }
    return answer
}

复杂度分析

时间复杂度：$O(n \log n)$。

空间复杂度：排序额外空间依语言实现，算法工作空间 $O(1)$。

关键点总结

[!green]

最优方案的中间边与最大边可以相邻；最小边却未必挨着它们，样例中的 2、8、9 正是这种情况。

易错点总结

[!yellow]

两短边之和必须严格大于最长边；三条边来自不同下标；不能套用最大周长三角形的相邻三元素贪心。

相似题目

题目	难度	关联与区别
976. 三角形的最大周长	简单	最大周长可检查相邻三边，最小周长不能照搬，本题还要在更早位置找最小合法边。
611. 有效三角形的个数	中等	共享排序后的三角形不等式 a+b>c，原题统计全部组合，本题选择最小周长。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/04517851

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！