Java合并相邻的数组元素以产生最大最小值

Question

请原谅我的标题令人困惑，我需要实现一个可以简化如下的算法:

给定一个整数数组，以及需要合并的次数(表示为k)，返回合并数组的最大最小值，合并只能与相邻元素发生。

例如array = [3,2,8,2,9], k = 2两次合并后数组的最大min值为5，合并后的数组为[5, 10, 9]。在此示例中，我们需要合并元素 3 & 2 和 8 & 2。

任何其他合并策略都会产生小于或等于 5 的最小值，例如:[5,8,11], [3,10,11], [13,2,9](合并的元素可以合并再次)

表示数据的最佳数据结构是什么？解决该问题的有效算法是什么？据我所知，需要在需要对数组的当前最小值及其较小的相邻元素之一进行合并的地方应用贪心算法。

编辑:我刚刚意识到贪心算法可能不适用，对于误导性的评论感到抱歉，如果它不区分与左元素或右元素合并，这将产生错误的答案。以此为例，给定一个数组 = [4,5,3,5]，我们需要移除 2 个元素。

有了贪心，[4,5,3,5] -> [4,8,5] -> [12,5]，所以答案是5；然而正确的答案应该是 8，合并顺序如下:

[4,5,3,5] -> [4,5,8] -> [9,8]

Answer 1

ValPosFrom 是一个简单的类，用于存储这些东西，from 是合并 from 的地方。您可以从 List = 3,2,6,3,2 和 k=1 之类的事物中获得不确定的结果，它将 2 分钟之一合并为 5 分钟，但哪一个并不重要。当所有位置的邻居值都是唯一的时，它会收敛。

    private static List<Integer> merge(List<Integer> things, int merges) {
    List<Integer> result = new ArrayList<>(things);
    for (int i = 0; i < merges; i++) {
        int min = Integer.MAX_VALUE;
        List<Integer> positions = new ArrayList<>();
        for (int j = 0; j < result.size(); j++) {
            if (result.get(j) < min) {
                positions.clear();
                positions.add(j);
                min = result.get(j);
            } else if (result.get(j) == min) {
                positions.add(j);
            }
        }
        List<ValPosFrom> neighbors = new ArrayList<>();
        positions.forEach(p -> {
            if (p - 1 >= 0) {
                neighbors.add(new ValPosFrom(result.get(p - 1), p - 1, p));
            }
            if (p + 1 < result.size()) {
                neighbors.add(new ValPosFrom(result.get(p + 1), p + 1, p));
            }
        });
        ValPosFrom vpf = Collections.min(neighbors, Comparator.comparingInt(v -> v.val));
        result.set(vpf.pos, result.get(vpf.pos) + result.get(vpf.from));
        result.remove(vpf.from);
    }
    return result;
}