Java合并相邻数组元素以获得最大最小值

Question

请原谅我混淆了标题，我需要实现一个算法，该算法可以简化如下：

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

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

任何其他合并策略都会产生与5较小或相等的min val，例如：[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是进行合并的地方。您可以从列表=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;
}