如何优化统计当前建筑后连续更矮建筑数量的O(n²)算法？

你的需求是统计每个建筑之后连续比它矮的建筑总数，原暴力遍历的O(n²)算法在n达到80000时会严重超时，这里用单调栈可以把时间复杂度降到O(n)，完美适配大数据量场景。

核心思路 #

我们需要为每个建筑找到后面第一个高度≥它的建筑位置：

• 如果找到这个位置j，那么该建筑贡献的连续矮建筑数量是j - i - 1（i是当前建筑的索引）
• 如果后面没有这样的建筑，贡献数量是数组长度 - i - 1

单调栈可以高效实现这个查找过程：维护一个保存索引的单调递增栈（栈中索引对应的建筑高度单调递增），遍历数组时，用当前建筑去触发栈中元素的结果计算，每个元素仅入栈、出栈一次，全程线性时间。

优化后的C++代码 #

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    vector<int> H = {5,3,4,2,6,1};
    int n = H.size();
    long long total_count = 0; // 用long long避免溢出，n=8e4时最大总和可能到~3e9
    stack<int> st;

    for (int i = 0; i < n; ++i) {
        // 弹出所有高度小于当前建筑的栈顶元素，计算它们的贡献
        while (!st.empty() && H[st.top()] < H[i]) {
            int idx = st.top();
            st.pop();
            total_count += i - idx - 1;
        }
        st.push(i);
    }

    // 处理栈中剩余的元素（后面没有≥它们的建筑）
    while (!st.empty()) {
        int idx = st.top();
        st.pop();
        total_count += n - idx - 1;
    }

    cout << "output = " << total_count << endl;
    return 0;
}

代码说明 #

1. 单调栈维护：栈中始终保存未找到第一个≥自身高度的建筑索引，且对应的高度单调递增。
2. 遍历计算：遇到当前建筑高度≥栈顶元素时，栈顶元素的第一个“阻挡物”就是当前建筑，直接计算它的连续矮建筑数量并累加。
3. 剩余元素处理：遍历结束后，栈中剩下的元素后面没有更高或相等的建筑，它们的贡献是从自身索引到数组末尾的元素个数减1。
4. 溢出防护：用long long存储总和，避免n=80000时总和超出int的范围（最大可能为80000*80000/2=3.2e9，超过int的2e9上限）。

复杂度对比 #

• 原算法：O(n²)，最坏情况（比如严格递减数组）需要遍历n*(n-1)/2次，n=8e4时计算量达3.2e9次，完全无法在合理时间内完成。
• 优化后算法：O(n)，每个元素仅入栈、出栈一次，计算量约8e4次，性能提升几个数量级。

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