Java桥梁构建解决方案返回错误结果求助

看起来你的桥梁计数代码出了点小问题，我来帮你梳理下问题所在，以及正确的解法～

问题核心分析 #

这个"最大桥梁数"的问题，本质是**最长递增子序列（LIS）**的经典应用场景。正确的解题逻辑应该是：

1. 先将所有CityPairs按照北岸城市编号升序排序；如果北岸编号相同，则按南岸城市编号升序排序（避免同北岸城市建桥冲突）
2. 提取排序后的南岸城市编号序列，找到这个序列的最长递增子序列的长度，就是能搭建的最大桥梁数

拿你的测试实例来看：
原始CityPairs列表：(6,2)、(4,3)、(2,6)、(1,5)
按北岸排序后应该是：(1,5)、(2,6)、(4,3)、(6,2)
对应的南岸序列是[5,6,3,2]，它的最长递增子序列是[5,6]，长度为2，这就是你要的预期结果。

你的代码可能存在的错误点 #

结合常见的错误情况，你的代码大概率在以下两个环节出了问题：

• 排序逻辑错误：没有正确按照北岸编号升序排序，或者排序时的比较器写反了顺序
• LIS计算错误：动态规划的状态转移逻辑有误，或者遍历顺序不对，导致没有找到真正的最长递增子序列

正确的完整代码示例 #

这里给你一份可以正确运行的代码，你可以对比自己的代码找差异：

class CityPairs {
    int north, south;
    public CityPairs(int north, int south) {
        this.north = north;
        this.south = south;
    }
}

class CityPairsDriver {
    // 计算最大桥梁数的核心方法
    static int maxBridges(CityPairs[] pairs) {
        // 第一步：按北岸升序排序，北岸相同则按南岸升序排序
        java.util.Arrays.sort(pairs, (a, b) -> {
            if (a.north != b.north) {
                return Integer.compare(a.north, b.north);
            } else {
                return Integer.compare(a.south, b.south);
            }
        });

        // 第二步：提取南岸序列，计算最长递增子序列长度
        int n = pairs.length;
        int[] lis = new int[n];
        // 初始化每个位置的LIS长度至少为1（自己本身）
        java.util.Arrays.fill(lis, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 如果当前南岸编号大于之前的，且LIS长度可以更新
                if (pairs[i].south > pairs[j].south && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }

        // 找到lis数组中的最大值，就是最大桥梁数
        int max = 0;
        for (int num : lis) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    // 测试方法
    public static void main(String[] args) {
        CityPairs[] pairs = {
            new CityPairs(6, 2),
            new CityPairs(4, 3),
            new CityPairs(2, 6),
            new CityPairs(1, 5)
        };
        System.out.println(maxBridges(pairs)); // 输出2，符合预期
    }
}

代码说明 #

1. 排序环节：使用Java8的Lambda表达式作为比较器，确保北岸编号从小到大排序，避免了排序逻辑错误
2. LIS计算：用动态规划的方式，lis[i]表示以第i个南岸城市结尾的最长递增子序列长度，通过两层循环遍历更新，最后取最大值就是结果

你可以把自己的代码和这份对比，重点检查排序逻辑和LIS的状态转移部分，应该就能找到问题所在啦～

内容的提问来源于stack exchange，提问作者okaSKR