8

在最近的一个面试问题中，我遇到了以下问题。

在一个特定的城市，我们有一排不同高度的建筑物。高度为 h 的建筑物倒塌会导致其右侧的下一个 h-1 建筑物也倒塌。建筑物的高度可以在 1 到 5000 之间。给定所有建筑物的高度（从左到右排列，即最左边的建筑物索引=1，最右边的建筑物索引=N），我们需要找出造成最大破坏的建筑物。

例如：

输入：建筑物数量：6

建筑物高度：2 1 3 3 1 6

答案应该建立在索引 3

我尝试的解决方案是使用复杂度为 O(N^2) 的蛮力技术。我所做的是对列表中的每座建筑物，我找出了它将摧毁的建筑物的数量。

可以为这个问题构建一个更好的解决方案吗？

4

5 回答 5

10

只需从左边开始，倒塌第一栋建筑，然后计算它造成的总伤害（*）。

从下一个建筑物（尚未倒塌）开始一次又一次地执行此操作。

从这些中，选择最大值。

复杂度：O(n)。

这种贪心算法之所以有效，是因为整个过程是一个连锁反应，如果建A迫使B倒塌，那么从B开始就无法获得更好的分数。

(*) 您可以通过维护一个计数器来存储右侧应该倒塌的建筑物数量。 counter = max(counter - 1, height of next building).

于 2013-09-25T11:49:25.453 回答
2

城市的一些区域起到“防火墙”的作用——崩溃在那个时候停止。稍加思考表明，这些是值 1 左侧的部分，其中高度增加（向左）每步不超过一次（如果您可以有 0 高度，这会使事情稍微复杂化）。

并且得分最高的区域必须在防火墙之后开始（因为如果没有，左侧就会有一个更高的区域）。

所以从右边扫描，找到这些防火墙，然后找到防火墙右侧的哪个部分损坏最大。这是 O(n) 因为它只是线性扫描（从右到左一次，然后每个部分一次，没有重叠）。

实际上，卡罗利的答案是等效的并且更易于实现。

于 2013-09-25T11:58:59.647 回答
1
  1. 从最右边的索引开始。
  2. 最后一栋建筑应造成 1 的破坏值。
  3. 向左迭代。

类似的东西（来自建筑 i 的破坏）

D[i] = 1 + min( N-i, max( index[i]-1, 0+D[i+1],1+D[i+2],... to index[i]-1 terms ) )
于 2013-09-25T11:45:57.970 回答
0

在 Java 中，不考虑后续的崩溃：

public static int collapse(int[] buildings) {
    int i, maxDamage, index, currentDamage;
    // do not consider the last building, it will cause only its own fall
    maxDamage = 1;
    index = buildings.length - 1;
    for(i = buildings.length - 1; i >= 0; i--) {
        // update maximum damage as the mimimum value between the building[i] (the height of the building at index i) and the remaining number of elements from i to the end of the array
        currentDamage = Math.min(buildings[i], buildings.length - i);
        System.out.println(currentDamage);
        if(currentDamage > maxDamage) {
            maxDamage = currentDamage;
            index = i;
        }
    }
    return index;
}

我的最终解决方案与接受的解决方案不同，顺便说一下，我并没有完全理解。这个想法是从最右边的位置开始计算当前索引将倒塌的建筑物的数量。

index:  7  6  5  4  3  2  1  0
height: 1  3  1  2  4  1  3  2
damage: 1  2  1  2  4  1  3  2

然后我只是从最右边的位置开始累积总和。我将当前位置倒塌的建筑物数量添加到倒塌的建筑物数量上，从右边的下一栋建筑物凝视直到最后都没有倒塌。

index:  7  6  5  4  3  2  1  0
height: 1  3  1  2  4  1  3  2
damage: 1  2  1  2  5  1  7  8

最后，我只返回最大伤害的索引。

该解决方案运行O(n)但使用了额外的O(n)空间。

下一个代码是完整版本（也适用于后续折叠）：

public static int collapse(int[] buildings) {
    int i, maxIndex, max;
    int damage[] = new int[buildings.length];
    for(i = buildings.length - 1; i >= 0; i--) {
        // compute damage for each position
        damage[i] = Math.min(buildings[i], buildings.length - i);
    }
    for(i = buildings.length - 1; i >= 0; i--) {
        // update total accumulated damage for each position
        if(damage[i] > 1) {
            if(damage[i] + i - 1 < buildings.length && i != (i + damage[i] - 1) ) {
                damage[i] += damage[i + damage[i] - 1] - 1;
            }
        }
    }
    max = damage[0];
    maxIndex = 0;
    for(i = 1; i < buildings.length; i++) {
        // find the maximum damage
        if(damage[i] > max) {
            max = damage[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}
于 2013-09-25T11:55:29.887 回答
0

与@Karoly 的答案相同的方法。在红宝石中：

def find_max_damage_index(buildings)

  max_damage = 0
  max_start_index = nil

  current_start_index = nil
  current_h = 0
  current_damage = 0

  buildings.each_with_index{|h,i|
    if current_h == 0 #end of batch
      if current_damage > max_damage
        max_damage = current_damage
        max_start_index = current_start_index
      end
      #start new batch
      current_h = h
      current_damage = 1
      current_start_index = i
    else
      current_h = h if h > current_h
      current_damage += 1
    end
    current_h -= 1
  }
  #last batch
  if current_damage > max_damage
    max_damage = current_damage
    max_start_index = current_start_index
  end

  return max_start_index
end
于 2013-09-25T12:09:59.063 回答