Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediummonotonic-stack

Sum of Subarray Minimums

Problem (restated)

For every non-empty contiguous subarray, take its minimum; return the sum of those minima mod 10^9+7.

Intuition

arr[i] is min of left[i]*right[i] subarrays (strict on one side to handle ties). Monotonic stack finds span.

Approaches

Contribution via next smaller

Tested only

Time O(n)Space O(n)

Idea. left[i] = distance to previous strictly smaller; right[i] = to next smaller-or-equal. ans += arr[i]leftright.

Walkthrough. [3,1,2,4] → 17.

Trade-offs. Brute O(n^2). Asymmetric </≤ avoids double-counting equal mins.

Solution

export function sumSubarrayMins(arr: number[]): number {
  const MOD = 1_000_000_007;
  const n = arr.length;
  const left = Array(n).fill(0);
  const right = Array(n).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && arr[stack[stack.length - 1]!]! > arr[i]!) stack.pop();
    left[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1]!;
    stack.push(i);
  }
  stack.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length && arr[stack[stack.length - 1]!]! >= arr[i]!) stack.pop();
    right[i] = stack.length === 0 ? n - i : stack[stack.length - 1]! - i;
    stack.push(i);
  }
  let ans = 0;
  for (let i = 0; i < n; i++) ans = (ans + arr[i]! * left[i]! * right[i]!) % MOD;
  return ans;
}

export function sumSubarrayMins(arr: number[]): number {
  const MOD = 1_000_000_007;
  const n = arr.length;
  const left = Array(n).fill(0);
  const right = Array(n).fill(0);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && arr[stack[stack.length - 1]!]! > arr[i]!) stack.pop();
    left[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1]!;
    stack.push(i);
  }
  stack.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length && arr[stack[stack.length - 1]!]! >= arr[i]!) stack.pop();
    right[i] = stack.length === 0 ? n - i : stack[stack.length - 1]! - i;
    stack.push(i);
  }
  let ans = 0;
  for (let i = 0; i < n; i++) ans = (ans + arr[i]! * left[i]! * right[i]!) % MOD;
  return ans;
}

Template connection

Monotonic stack contribution technique.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?