如何优化建筑视野计数程序的时间复杂度（O(n²)降阶）

问题回顾 #

需要统计满足以下两个条件的建筑位置数量：

1. 第i栋建筑前方所有高度≤它的建筑数量不超过K[i]；
2. 第i栋建筑前方不存在高度大于它的建筑。

约束：数组长度1_{10^5，元素值1}10^5，原O(n²)代码无法处理大规模数据。

核心观察 #

条件2等价于：第i栋建筑是从数组起点到i位置的前缀最大值（允许等于之前的最大值）。因为如果前方存在更高建筑，i就不可能是前缀最大值；反之，若i是前缀最大值，前方必然没有更高建筑。

同时，若i是前缀最大值，前方所有建筑的高度都≤它，因此条件1中的计数就是i（前方共有i栋建筑）。

优化算法思路 #

1. 维护一个变量记录当前遍历到的最大高度maxHeight；
2. 遍历每个建筑位置i：
   • 若当前建筑高度大于maxHeight：它是新的前缀最大值，计数为i，检查是否≤K[i]，符合则计数加1，更新maxHeight；
   • 若当前建筑高度等于maxHeight：前方无更高建筑，计数为i，检查是否≤K[i]，符合则计数加1；
   • 若当前建筑高度小于maxHeight：前方存在更高建筑，直接跳过。

该算法仅需一次遍历，时间复杂度O(n)，空间复杂度O(1)，完美适配大规模数组。

优化后的Java代码 #

public static int optimizedProcess(int[] buildings, int[] K) {
    int n = buildings.length;
    int answer = 0;
    int maxHeight = -1; // 建筑高度≥1，初始值设为-1
    
    for (int i = 0; i < n; i++) {
        int current = buildings[i];
        if (current > maxHeight) {
            if (i <= K[i]) {
                answer++;
            }
            maxHeight = current;
        } else if (current == maxHeight) {
            if (i <= K[i]) {
                answer++;
            }
        }
        // current < maxHeight时直接跳过
    }
    return answer;
}

验证示例 #

以题目示例B = [2,1,3]，K = [1,2,1]为例：

• i=0：2>-1，i=0≤1，answer=1，maxHeight=2；
• i=1：1<2，跳过；
• i=2：3>2，i=2>1，不计数；
  最终answer=1，与示例结果一致。

内容的提问来源于stack exchange，提问作者Learner