时间戳

首页 > 解决方案 > 递归地最小化塔之间的最大差异

java - 递归地最小化塔之间的最大差异

问题描述

给定 n 个塔的高度和一个值 k。我们需要将每个塔的高度增加或减少 k（仅一次），其中 k > 0。任务是最小化修改后最长和最短塔的高度之间的差异，并输出此差异。

输入 {1, 5, 15, 10}

K = 3

输出为 8

输入 {1, 10, 14, 14, 14, 15}

K = 6

输出为 5

我意识到这可以通过 DP 技术/贪婪技术来解决。谁能帮我通过递归解决这个问题。下面的示例代码片段。感谢您的回复。

public class TowerHeights {
    public static void main(String[] args) {
        int[] towerHeight = {1,5,15,10};
        int k = 3;
        Arrays.sort(towerHeight);
        int min = towerHeight[0] + k;
        int max = towerHeight[towerHeight.length-1] - k;
        minimize(towerHeight,1,k,min,max);
    }

    public static void minimize(int[] towerHeight, int index, int k, int min, int max){
        if(index<=towerHeight.length-2){

            //I need help in completing this function recursively
        }
    }
}

问题参考： https ://www.geeksforgeeks.org/minimize-the-maximum-difference-between-the-heights/

标签： javarecursion

解决方案

我认为这不是 DP 或贪婪的子问题的问题。要以递归方式解决，请尝试这种方式，例如使用递归进行循环

public static int minimize(int[] towerHeight, int index, int k, int min, int max){
    if(index<=towerHeight.length-2){
        int subtract = towerHeight[index] - k; 
        int add = towerHeight[index] + k; 
        if (!(subtract >= min || add <= max)){
             if (max - subtract <= add - min) min = subtract; 
             else max = add;
        }
        return Math.min(minimize(towerHeight,index+1,k,min,max), max - min);
    }
    else {
        return max-min;
    }
}

推荐阅读