Monoton Yığın

Nasıl düşünülür

Değerleri monoton (artan veya azalan) indekslerin yığınını tut. Yeni değer sırayı bozunca pop et ve o indeksleri çöz: yeni gelen onların sonraki büyük/küçüğü. Her indeks en fazla bir push/pop görür.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Sağda sonraki büyük	top < current iken pop	Answer[top]=current
Sonraki küçük	Karşılaştırmayı çevir	Aynı yapı
Histogram	Önceki + sonraki küçük	Genişlik = R-L-1

Karmaşıklık temeli

O(n) zaman (amortize her indeks bir push/pop), O(n) yığın alanı.

Şablondan probleme

1. Yön (sol→sağ veya sağ→sol) ve monoton sırayı seç.
2. Dolaş; yığın tepesi current ile çözülebilirse pop et ve cevabı yaz.
3. Current indeksi push et.
4. Kalan yığını sentinel cevaplarla (-1 veya n) boşalt.

/** Monotonic stack template: next greater element to the right (−1 if none). */
export function nextGreater(nums: number[]): number[] {
  const n = nums.length;
  const ans = new Array<number>(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack.at(-1)!]! < nums[i]!) {
      ans[stack.pop()!] = nums[i]!;
    }
    stack.push(i);
  }
  return ans;
}

/** Monotonic stack template: next greater element to the right (−1 if none). */
export function nextGreater(nums: number[]): number[] {
  const n = nums.length;
  const ans = new Array<number>(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack.at(-1)!]! < nums[i]!) {
      ans[stack.pop()!] = nums[i]!;
    }
    stack.push(i);
  }
  return ans;
}