Maximal Rectangle

Problem (yeniden ifade)

‘0’/‘1’ ikili matrisi. Yalnızca 1 içeren en büyük dikdörtgenin alanını döndür.

Sezgi

Her satırı bir histogram tabanı olarak ele al: heights[c] = yukarı doğru ardışık 1’ler. Satır başına histogramdaki en büyük dikdörtgen (monoton yığın); max’ı al.

Yaklaşımlar

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

Şablon bağlantısı

Her satırda monoton yığın histogramı (LC84).

Derinlemesine

Her satırı bir histogram tabanı olarak ele al: matrix[r][c] == '1' ise heights[c] = heights[c] + 1, değilse 0’a sıfırla. Satır r için histogramı güncelledikten sonra histogramdaki en büyük dikdörtgeni (LC 84) çalıştır. Cevap tüm satırlar üzerindeki max. Bu, 2D bir problemi 1D monoton-yığın şablonunun rows çağrısına indirger.

Yansıma

• Her satır, üstündeki ardışık 1’lerin yüksekliği. 0 görünce o sütun neden sıfırlanır?
• Satır histogramını LC84 yığınına vermek. Boş matris ve tek 0 hücresi.
• Köşegen 1’ler yükseklik biriktirmez; cevap 1. Tam 1’ler dikdörtgeni rows · cols.