数组查询：统计以指定索引为端点且元素为段内最大值的段数

问题分析 #

给定一个包含N个整数的数组，回答K个查询。每个查询给出数组的1-based索引X，需要计算满足以下两个条件的段的数量：

1. 段的左端点是X，且X处的元素≥段内所有元素；
2. 段的右端点是X，且X处的元素≥段内所有元素。

注意：段[X]会同时满足上述两个条件，因此统计时需要减去重复计数的1次。

示例验证 #

输入数组{4,2,1,3}，查询{1,4}：

• 索引1（元素4）的有效段：[4]、[4,2]、[4,2,1]、[4,2,1,3] → 共4个；
• 索引4（元素3）的有效段：[3]、[1,3]、[2,1,3] → 共3个。

高效解法思路 #

暴力解法的时间复杂度为O(n*k)，当n和k较大时效率极低。我们可以通过单调栈预处理，将时间复杂度优化到O(n + k)：

核心步骤 #

1. 预处理left数组：对于每个索引i（1-based），left[i]表示左边第一个比A[i]大的元素的索引（若不存在则为0，对应虚拟的无穷大元素）。
   • 以i为右端点的有效段数量为i - left[i]（左端点范围是left[i]+1到i）。
2. 预处理right数组：对于每个索引i（1-based），right[i]表示右边第一个比A[i]大的元素的索引（若不存在则为n+1，对应虚拟的无穷大元素）。
   • 以i为左端点的有效段数量为right[i] - i（右端点范围是i到right[i]-1）。
3. 计算查询结果：对于每个查询X，结果为(right[X] - X) + (X - left[X]) - 1（减去1是因为[X]被重复计数）。

单调栈实现原理 #

单调栈用于维护一个单调递减的索引序列，确保我们能在O(1)时间内找到每个元素左右第一个更大的元素：

• 计算left数组时，从左到右遍历数组，弹出栈中所有值≤当前元素的索引，栈顶即为左边第一个更大元素的索引；
• 计算right数组时，从右到左遍历数组，弹出栈中所有值≤当前元素的索引，栈顶即为右边第一个更大元素的索引。

代码实现（Python） #

def solve():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    original_array = list(map(int, input[ptr:ptr+n]))
    ptr += n
    # 转换为1-based数组，左右添加无穷大虚拟元素处理边界
    A = [float('inf')] + original_array + [float('inf')]
    k = int(input[ptr])
    ptr += 1
    queries = list(map(int, input[ptr:ptr+k]))
    
    # 预处理left数组：左边第一个比当前元素大的索引
    left = [0] * (n + 2)
    stack = [0]  # 栈底初始为0（对应无穷大元素）
    for i in range(1, n + 1):
        while A[stack[-1]] <= A[i]:
            stack.pop()
        left[i] = stack[-1]
        stack.append(i)
    
    # 预处理right数组：右边第一个比当前元素大的索引
    right = [n + 1] * (n + 2)
    stack = [n + 1]  # 栈底初始为n+1（对应无穷大元素）
    for i in range(n, 0, -1):
        while A[stack[-1]] <= A[i]:
            stack.pop()
        right[i] = stack[-1]
        stack.append(i)
    
    # 处理所有查询
    result = []
    for x in queries:
        count = (right[x] - x) + (x - left[x]) - 1
        result.append(str(count))
    print(' '.join(result))

if __name__ == "__main__":
    solve()

复杂度分析 #

• 预处理阶段：每个元素入栈和出栈各一次，时间复杂度O(n)；
• 查询阶段：每个查询仅需O(1)计算，总时间复杂度O(k)；
• 整体时间复杂度：O(n + k)，空间复杂度O(n)（用于存储left、right数组和栈）。

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