寻求O(n)时间计算数组所有子区间最大差值之和的算法或可行性证明方向

Hey there! Let's break this problem down step by step—you're already halfway there with your O(nlogn) solution, and the O(n) approach is totally achievable once you reframe the problem a bit.

First, let's split your original problem into two independent subproblems—this is the key insight that unlocks the O(n) solution:

• Calculate the sum of maximum values across all subarrays (let's call this S_max)
• Calculate the sum of minimum values across all subarrays (let's call this S_min)

Your final answer will simply be S_max - S_min. Separating these two tasks makes the problem far easier to tackle than trying to compute the max-min difference directly for every subarray.

Using Monotonic Stacks for O(n) Calculation of S_max (and S_min) #

The core idea here is to figure out, for each element a[i], how many subarrays have a[i] as their maximum (or minimum, for S_min). Multiply that count by a[i], and sum across all elements to get the total sum.

Step-by-Step for S_max: #

1. Find boundary indices for each element:

   • For a[i], find left[i]: the index of the first element to the left that is strictly greater than a[i]. If no such element exists, set left[i] = -1.
   • Find right[i]: the index of the first element to the right that is greater than or equal to a[i]. If no such element exists, set right[i] = n (where n is the length of the array).

   Note: Using "strictly greater" on the left and "greater than or equal" on the right ensures we don't double-count subarrays with duplicate elements. You could also reverse the conditions (>= on left, > on right)—just pick one consistent rule to avoid overlaps.

2. Count valid subarrays:
   The number of subarrays where a[i] is the maximum is (i - left[i]) * (right[i] - i).

   • i - left[i]: Number of choices for the subarray's left endpoint (any position from left[i]+1 to i)
   • right[i] - i: Number of choices for the subarray's right endpoint (any position from i to right[i]-1)
   • Multiply these two to get all combinations of valid subarrays centered around a[i] as the max.

3. Sum up contributions:
   Iterate through every element, add a[i] * (i - left[i]) * (right[i] - i) to S_max.

4. Repeat for S_min:
   For the minimum sum, just flip the comparison rules:

   • left[i]: First element to the left strictly less than a[i]
   • right[i]: First element to the right less than or equal to a[i]
     Follow the same counting and summing steps to get S_min.

Why this is O(n) time: #

Monotonic stacks (the data structure we use to find left[i] and right[i] efficiently) operate in linear time. Each element is pushed to the stack exactly once and popped exactly once—no nested loops, just a single pass over the array for left boundaries, and another single pass for right boundaries.

For example, to compute left[i]:

• Initialize an empty stack, then iterate from left to right
• For each a[i], pop all stack elements that are <= a[i] (they can't be the first greater element to the left)
• The remaining stack top is left[i] (or -1 if the stack is empty)
• Push i onto the stack

Is an O(n) solution possible? #

Absolutely—this monotonic stack approach is a proven O(n) method, so the problem can be solved in linear time. If you weren't aware of using monotonic stacks for "element contribution" problems, that's likely the missing piece in your earlier attempts.

Quick tips to avoid mistakes: #

• Double-check your boundary conditions for duplicate elements—this is where most off-by-one errors happen.
• Handle edge cases (empty array, single-element array) explicitly (the sum will be 0 in both cases).

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