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

Let's break down this problem and find an efficient solution that avoids the O(n*k) brute-force approach. First, let's make sure we understand the requirements clearly:

We have an array of integers, and for each query (which gives a 1-based index X), we need to count how many valid line segments exist where:

• The segment starts at X OR ends at X
• The element at X is greater than or equal to every element in the segment

Why Brute-force is Bad #

The brute-force method would check every possible segment starting or ending at X for each query, which leads to O(n*k) time complexity. For large n and k (like 10^5 elements and queries), this will be way too slow. So we need a way to precompute answers for all positions in O(n) time, then answer queries in O(1) each.

Key Insight: Monotonic Stacks for Boundary Detection #

The core idea is to find, for each element arr[i], the boundaries of the largest interval where arr[i] is the maximum (or equal to the maximum). Specifically:

• Left Boundary (L[i]): The index of the first element to the left of i that is strictly larger than arr[i]. If no such element exists, L[i] = -1.
• Right Boundary (R[i]): The index of the first element to the right of i that is strictly larger than arr[i]. If no such element exists, R[i] = n (where n is the length of the array).

Once we have these boundaries, the number of valid segments for position i is calculated as:
R[i] - L[i] - 1

Let's verify this with the examples:

1. For the array {1,2,3}:
   • Element 3 (index 2, 0-based): L[2] = -1, R[2] = 3. So 3 - (-1) -1 = 3, which matches the 3 valid segments.
   • Element 2 (index 1): L[1] = -1, R[1] = 2. 2 - (-1) -1 = 2, which matches the 2 valid segments.
2. For the input array {4,2,1,3}:
   • Query index 1 (0-based 0): L[0] = -1, R[0] =4. 4 - (-1)-1=4, which is correct.
   • Query index4 (0-based3): L[3]=0, R[3]=4. 4-0-1=3, which is correct.

How to Compute L and R with Monotonic Stacks #

We use monotonic stacks to efficiently find these boundaries in linear time. A monotonic stack maintains elements in a strictly decreasing order (since we're looking for the first larger element).

Calculating Left Boundaries (L[i])

• Initialize an empty stack (stores indices, not values)
• Iterate from left to right:
  • While the stack isn't empty and the element at the stack's top is <= current element, pop from the stack (these elements can't be the first larger element for any future positions)
  • If the stack is empty, L[i] = -1; else, L[i] = stack's top index
  • Push the current index onto the stack

Calculating Right Boundaries (R[i])

• Initialize an empty stack
• Iterate from right to left:
  • While the stack isn't empty and the element at the stack's top is <= current element, pop from the stack
  • If the stack is empty, R[i] = n; else, R[i] = stack's top index
  • Push the current index onto the stack

Implementation Code (Python) #

def precompute_answers(arr):
    n = len(arr)
    left_bound = [-1] * n
    stack = []
    
    # Compute left boundaries (first element > arr[i] to the left)
    for i in range(n):
        while stack and arr[stack[-1]] <= arr[i]:
            stack.pop()
        if stack:
            left_bound[i] = stack[-1]
        stack.append(i)
    
    right_bound = [n] * n
    stack = []
    
    # Compute right boundaries (first element > arr[i] to the right)
    for i in range(n-1, -1, -1):
        while stack and arr[stack[-1]] <= arr[i]:
            stack.pop()
        if stack:
            right_bound[i] = stack[-1]
        stack.append(i)
    
    # Calculate answers for each position
    answers = [right_bound[i] - left_bound[i] - 1 for i in range(n)]
    return answers

# Example usage
arr = [4, 2, 1, 3]
queries = [1, 4]
precomputed = precompute_answers(arr)
# Convert queries from 1-based to 0-based
results = [precomputed[q-1] for q in queries]
print(" ".join(map(str, results)))  # Output: 4 3

Time Complexity #

• Preprocessing: O(n) — each element is pushed and popped from the stack exactly once.
• Queries: O(k) — each query is a constant-time lookup after preprocessing.

This approach is efficient enough even for large input sizes, making it a significant improvement over the brute-force method.

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