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 (yeniden ifade)

Her boş olmayan bitişik alt dizi için minimumunu al; bu minimumların toplamını mod 10^9+7 döndür.

Sezgi

arr[i], left[i]*right[i] alt dizinin min’idir (eşitlikler için bir tarafta sıkı). Monotonic stack span’i bulur.

Yaklaşımlar

Sonraki daha küçük ile katkı

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. left[i] = önceki sıkı daha küçüğe uzaklık; right[i] = sonraki smaller-or-equal’a. ans += arr[i]leftright.

Yürüyüş. [3,1,2,4] → 17.

Trade-off. Brute O(n^2). Asimetrik </≤ eşit min’lerin çift sayılmasını önler.

Çözüm

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;
}

Şablon bağlantısı

Monotonic stack katkı tekniği.

Yansıma

Her i bir minimum. Solda ve sağda ilk daha küçük sınır. Alt dizi sayısı (i-left)·(right-i).
Eşit değerler: bir taraf strict, öbürü değil. İkisi de < olursa aynı minimum iki kez sayılır.
Mod çarpımdan önce taşmasın. Sentinel −1 ve n. Tek eleman: cevap kendisi.