时间戳

首页 > 解决方案 > 最多两个横幅的最小总面积以覆盖 N 个建筑物

javascript - 最多两个横幅的最小总面积以覆盖 N 个建筑物

问题描述

我正在做这个任务：

沿路有N座长方形建筑并排而立。第K个建筑物的大小为H k × 1。

由于计划对所有建筑物进行翻新，我们希望用矩形横幅覆盖它们，直到翻新完成。当然，要覆盖建筑物，横幅必须至少与建筑物一样高。如果它的宽度大于 1，我们可以用横幅覆盖多个建筑物。

例如，要覆盖高度为 3、1、4 的建筑物，我们可以使用大小为 4×3（即高度为 4，宽度为 3）的横幅，这里用蓝色标记：

尺寸为（3×1）、（1×1）、（4×1）的建筑物，覆盖着尺寸为4×3的脚手架

我们最多可以订购两个横幅，我们想覆盖所有的建筑物。此外，我们希望尽量减少制作横幅所需的材料量。

最多两个横幅覆盖所有建筑物的最小总面积是多少？

写一个函数：

function solution(H);

即，给定一个由N个整数组成的数组H，返回我们必须订购的最多两个横幅的最小总面积。

例子：

  1. 给定H = [3, 1, 4]，该函数应返回 10。结果可以通过覆盖前两座建筑物的横幅大小为 3×2 和第三座建筑物的横幅大小为 4×1 来实现：
    示例说明

  2. 给定H = [5, 3, 2, 4]，该函数应返回 17。结果可以通过用大小为 5×1 的横幅覆盖第一座建筑物并用大小为 4×3 的横幅覆盖其他建筑物来实现：

  3. 给定H = [5, 3, 5, 2, 1]，您的函数应该返回 19。结果可以通过用大小为 5×3 的横幅覆盖前三座建筑物，用大小为 2 的横幅覆盖另外两座建筑物来实现×2：
    示例说明

  4. 给定H = [7, 7, 3, 7, 7]，您的函数应该返回 35。结果可以通过使用一个大小为 7×5 的横幅来实现：
    示例说明

为以下假设编写一个有效的算法：

N是 [1..100,000] 范围内的整数；数组H的每个元素 都是 [1..10,000] 范围内的整数。

这是我尝试过的：

function solution(H){
    let length = H.length;
    let maxFromLeft = []
    let  maxFromRight = []
    maxFromLeft.length = length+1
    maxFromRight.length = length+1
    
    let currentMax = 0;
    for(let i =0; i< length; i++){
        currentMax = currentMax >= H[i] ? currentMax:H[i]
        maxFromLeft.push(currentMax)
    }
    currentMax =0
    for(let i=length-1; i> -1; i--){
        currentMax= currentMax >= H[i] ? currentMax : H[i]
        maxFromRight.push(currentMax)
    }
    let result = Number.MAX_VALUE;
    for(let i=0; i< length; i++){
        
       result = Math.min(result, maxFromLeft[i] * i  + maxFromRight[i]*(length-1)) 
       
    }
    console.log(result)
    return result   
}

solution([3,1,4]);

我的结果返回 NaN。我在哪里做错了？

标签： javascriptalgorithmdata-structures

解决方案

一些问题：

  • 输出的原因NaN是您初始化了两个数组的长度，这意味着您有带有空槽的数组。当您push在此类数组上执行时，那些推送的值将附加在这些空槽之后。您不应该设置这些length属性。push会做必要的...

  • maxFromRight[i]*(length-1)在两个方面是错误的：首先它应该从末尾获取条目，因此索引应该length-1-i改为 if i，并且乘法也应该是可变的，并且也-i应该是：它应该是maxFromRight[length-1-i]*(length-1-i)

  • 对于 的相同值，和i的值包括对 的考虑。不应该有这样的重叠。应该用作两个部分之间的明确划分。所以你可以定义建筑属于分裂的第二部分而不是第一部分。要做到这一点，请确保其中的第一个值为0：您可以通过重新排序语句来实现这一点。maxFromLeft[i]maxFromRight[i] H[i]iimaxFromLeft

我会假设横幅必须并排，而不是在彼此之上。

这是应用了修复程序的代码：

function solution(H){
    let length = H.length;
    let maxFromLeft = []
    let  maxFromRight = []
    // Remove the lines that set the length!
    
    let currentMax = 0;
    for(let i =0; i< length; i++){
        // next two lines switched, so first entry is 0
        maxFromLeft.push(currentMax)
        currentMax = currentMax >= H[i] ? currentMax:H[i]
    }
    currentMax =0
    for(let i=length-1; i> -1; i--){
        currentMax= currentMax >= H[i] ? currentMax : H[i]
        maxFromRight.push(currentMax)
    }
    let result = Number.MAX_VALUE;
    for (let i=0; i < length; i++){
       result = Math.min(result, maxFromLeft[i] * i  + maxFromRight[length-1-i]*(length-i)) // fix 
    }
    console.log(result)
    return result
   
}

solution([3, 1, 4]); 
solution([5, 3, 2, 4]); 
solution([5, 3, 5, 2, 1]); 
solution([7, 7, 3, 7, 7]);

推荐阅读