求数组子区间max(A子段)=min(B子段)的(l,r)对数，优化O(n²)算法

给定两个长度为n的数组a和b，需找出满足1≤l≤r≤n的区间对(l,r)的数量，使得a[l..r]的最大值等于b[l..r]的最小值。现有一段时间复杂度为O(n²)的代码如下：

int answer = 0;

for (int i = 0; i < n - 1; i++) {
    int l = i;
    int r = l;
    while (r < n) {
        int a_t = query(A, l, r, false); // 区间最大值
        int b_t = query(B, l, r, true);  // 区间最小值

        if (a_t == b_t) {
            answer++;
            r++;
        } else if (a_t > b_t) {
            break;
        } else {
            r++;
        }
    }
}

当然存在优化方法，能将时间复杂度从O(n²)降至O(n log n)甚至O(n)，核心是利用区间最值的单调性特性，结合预处理结构或单调栈减少重复计算：

方案一：稀疏表预处理区间最值 #

1. 预处理阶段：
   • 给数组a构建稀疏表，用于O(1)时间查询任意区间的最大值，预处理时间为O(n log n)。
   • 给数组b构建稀疏表，用于O(1)时间查询任意区间的最小值，预处理时间同样为O(n log n)。
2. 查询阶段：
   • 沿用原代码的双指针逻辑，但每次区间最值查询直接通过稀疏表完成，整体时间复杂度变为O(n + n log n) = O(n log n)，比原O(n²)效率提升显著。

方案二：单调栈+区间范围统计 #

这种方法能实现O(n)的时间复杂度，思路如下：

1. 用单调栈定位最值区间：
   • 对数组a，找出每个元素作为区间最大值的最大覆盖范围[L1[i], R1[i]]——即所有包含i且最大值为a[i]的区间，左端点不能小于L1[i]，右端点不能大于R1[i]。
   • 对数组b，找出每个元素作为区间最小值的最大覆盖范围[L2[j], R2[j]]——即所有包含j且最小值为b[j]的区间，左端点不能小于L2[j]，右端点不能大于R2[j]。
2. 统计符合条件的区间：
   • 遍历所有可能的数值x，收集数组a中值为x的位置集合，以及数组b中值为x的位置集合。
   • 对每个x，计算两类区间范围的交集，统计满足「区间[l,r]的a最大值为x且b最小值为x」的数量，最终累加所有x对应的数量得到答案。

原代码的小修正 #

原代码的循环条件i < n - 1会漏掉左端点为n-1的区间（即l=r=n-1的情况），应修改为i < n，避免统计遗漏。

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