多次查询数组排除指定连续区间后的最大最小元素差值的高效算法

核心思路 #

每次查询删除连续一段元素后，剩余元素只会是以下三种情况之一：

• 仅保留原数组的前缀部分
• 仅保留原数组的后缀部分
• 同时保留原数组的前缀和后缀两部分
  因此我们只需要提前预处理出前缀、后缀的最大值和最小值数组，每次查询就可以直接取值计算，不需要遍历数组。

预处理步骤 #

我们对长度为n的数组a，提前生成4个预处理数组（均为0-based索引）：

• pre_max[i]：从数组开头到下标i位置的所有元素的最大值
• pre_min[i]：从数组开头到下标i位置的所有元素的最小值
• suf_max[i]：从下标i位置到数组末尾的所有元素的最大值
• suf_min[i]：从下标i位置到数组末尾的所有元素的最小值
  四个数组都可以通过一次遍历生成，时间复杂度为O(n)。

查询逻辑 #

假设每次查询传入的是1-based的连续删除区间[L, R]，先转换为0-based的索引L0 = L-1、R0 = R-1，再分情况计算：

1. 删除区间包含整个数组：差值为0（无实际查询意义可跳过）
2. 删除区间从数组开头开始：仅保留R0+1到末尾的后缀，差值为 suf_max[R0+1] - suf_min[R0+1]
3. 删除区间到数组末尾结束：仅保留开头到L0-1的前缀，差值为 pre_max[L0-1] - pre_min[L0-1]
4. 同时保留前缀和后缀：总最大值为max(pre_max[L0-1], suf_max[R0+1])，总最小值为min(pre_min[L0-1], suf_min[R0+1])，差值为总最大值减总最小值
   单次查询时间复杂度为O(1)。

代码示例 #

a = [4, 5, 2, 1, 3, 4]
n = len(a)

# 预处理前缀数组
pre_max = [0] * n
pre_min = [0] * n
pre_max[0] = pre_min[0] = a[0]
for i in range(1, n):
    pre_max[i] = max(pre_max[i-1], a[i])
    pre_min[i] = min(pre_min[i-1], a[i])

# 预处理后缀数组
suf_max = [0] * n
suf_min = [0] * n
suf_max[-1] = suf_min[-1] = a[-1]
for i in range(n-2, -1, -1):
    suf_max[i] = max(suf_max[i+1], a[i])
    suf_min[i] = min(suf_min[i+1], a[i])

# 查询函数，L、R为1-based的删除区间
def query(L, R):
    L0 = L - 1
    R0 = R - 1
    if L0 == 0 and R0 == n-1:
        return 0
    if L0 == 0:
        return suf_max[R0+1] - suf_min[R0+1]
    if R0 == n-1:
        return pre_max[L0-1] - pre_min[L0-1]
    total_max = max(pre_max[L0-1], suf_max[R0+1])
    total_min = min(pre_min[L0-1], suf_min[R0+1])
    return total_max - total_min

# 测试示例：删除第2到第3个元素
print(query(2, 3)) # 输出3，符合预期

复杂度说明 #

• 预处理时间：O(n)，仅需要执行一次
• 单次查询时间：O(1)，支持任意次数的高频查询
• 空间复杂度：O(n)，存储4个预处理数组

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