İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarTekrarlarHakkında
Dil
EnglishTürkçe

Monoton Yığın

Rehber 2 / 6 · Yol 2 / 6

← ÖncekiSonraki →

Bu yazı henüz İngilizce. Arayüz Türkçe; içerik çevirisi sürüyor.

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

Hardmonotonic-stack

Maximal Rectangle

Problem (restated)

Binary matrix of ‘0’/‘1’. Return the area of the largest rectangle containing only 1s.

Intuition

Treat each row as the base of a histogram: heights[c] = consecutive 1s upward. Largest rectangle in histogram (monotonic stack) per row; take max.

Approaches

Histogram per row + stack

Tested only
Time O(mn)Space O(n)

Idea. Reset height on ‘0’. Same stack template as LC84.

Walkthrough. A block of ones spanning 2×3 → area 6 when the bottom row sees heights [2,2,2].

Trade-offs. DP left/right/up also O(mn); stack reuses LC84.

Solution
export function maximalRectangle(matrix: string[][]): number {
  if (!matrix.length || !matrix[0]!.length) return 0;
  const m = matrix.length, n = matrix[0]!.length;
  const heights = Array(n).fill(0);
  let best = 0;
  const largestRectangle = (h: number[]): number => {
    const stack: number[] = [];
    let ans = 0;
    for (let i = 0; i <= h.length; i++) {
      const cur = i === h.length ? 0 : h[i]!;
      while (stack.length && cur < h[stack[stack.length - 1]!]!) {
        const height = h[stack.pop()!]!;
        const left = stack.length ? stack[stack.length - 1]! : -1;
        ans = Math.max(ans, height * (i - left - 1));
      }
      stack.push(i);
    }
    return ans;
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) heights[c] = matrix[r]![c] === "1" ? heights[c]! + 1 : 0;
    best = Math.max(best, largestRectangle(heights));
  }
  return best;
}

export function maximalRectangle(matrix: string[][]): number {
  if (!matrix.length || !matrix[0]!.length) return 0;
  const m = matrix.length, n = matrix[0]!.length;
  const heights = Array(n).fill(0);
  let best = 0;
  const largestRectangle = (h: number[]): number => {
    const stack: number[] = [];
    let ans = 0;
    for (let i = 0; i <= h.length; i++) {
      const cur = i === h.length ? 0 : h[i]!;
      while (stack.length && cur < h[stack[stack.length - 1]!]!) {
        const height = h[stack.pop()!]!;
        const left = stack.length ? stack[stack.length - 1]! : -1;
        ans = Math.max(ans, height * (i - left - 1));
      }
      stack.push(i);
    }
    return ans;
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) heights[c] = matrix[r]![c] === "1" ? heights[c]! + 1 : 0;
    best = Math.max(best, largestRectangle(heights));
  }
  return best;
}

Template connection

Monotonic stack histogram (LC84) on each row.

Deep dive

Treat each row as the base of a histogram: heights[c] = heights[c] + 1 if matrix[r][c] == '1', else reset to 0. After updating the histogram for row r, run largest rectangle in histogram (LC 84). The answer is the max over all rows. This reduces a 2D problem to rows calls of the 1D monotonic-stack template.

Reflection