🧱 초보자용 가이드 'Maximal Rectangle' – LeetCode 85 (C++, Python, JavaScript)

I’m happy to help translate the article, but it looks like the body of the text isn’t included in your message—only the source link is present. Could you please provide the article’s content (or the specific sections you’d like translated)? Once I have the text, I’ll translate it into Korean while preserving the original formatting and code blocks.

문제 요약

주어진 것

• '0'와 '1' 문자로 채워진 2‑D 이진 matrix.

목표

• '1'만으로 이루어진 가장 큰 직사각형을 찾아 그 면적을 반환한다.

예시

Input:  matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6
Explanation: The maximal rectangle is shown in the picture above.

설명: 위 그림에 최대 직사각형이 표시되어 있습니다.

직관

모든 가능한 직사각형을 직접 확인하는 것은 현실적이지 않다.
대신 각 행을 바닥으로 간주하고 그 위에 쌓인 연속된 '1'들의 높이를 계산한다.
각 행은 히스토그램이 된다.

히스토그램에서 가장 큰 직사각형을 찾을 수 있다면, 이 과정을 모든 행에 대해 반복할 수 있다.
단조 스택을 사용하면 선형 시간에 필요한 정보를 얻을 수 있다:

인덱스 i에 있는 바에 대해:

width  = NSE[i] - PSE[i] - 1
area   = heights[i] * width

모든 행에 대한 최대 면적이 답이다.

코드 블록

C++ 솔루션

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        if (matrix.empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();

        vector heights(m, 0), pse(m), nse(m);
        stack ps, ns;
        int max_area = 0;

        for (int i = 0; i  heights[j]) {
                    nse[ns.top()] = j;
                    ns.pop();
                }
                ns.push(j);

                while (!ps.empty() && heights[ps.top()] >= heights[j]) {
                    ps.pop();
                }
                pse[j] = (ps.empty() ? -1 : ps.top());
                ps.push(j);
            }

            // Update max area for this histogram
            for (int j = 0; j  int:
        if not matrix:
            return 0

Python (부분 스니펫)

int:
    if not matrix:
        return 0

Python 솔루션

def maximalRectangle(matrix):
    if not matrix:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    max_area = 0

    for i in range(rows):
        # Update heights based on the current row
        for j in range(cols):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0

        # Largest Rectangle in Histogram for this row
        stack = []
        pse = [-1] * cols
        nse = [cols] * cols

        # Next Smaller Element
        for j in range(cols):
            while stack and heights[stack[-1]] > heights[j]:
                nse[stack.pop()] = j
            stack.append(j)

        # Previous Smaller Element (backwards pass)
        stack.clear()
        for j in range(cols - 1, -1, -1):
            while stack and heights[stack[-1]] > heights[j]:
                pse[stack.pop()] = j
            stack.append(j)

        # Compute area for each bar
        for j in range(cols):
            area = heights[j] * (nse[j] - pse[j] - 1)
            max_area = max(max_area, area)

    return max_area

JavaScript 솔루션 (버전 1)

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (let i = 0; i  heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Previous Smaller Element (reverse pass)
        stack.length = 0; // clear stack
        for (let j = cols - 1; j >= 0; --j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute area for each bar
        for (let j = 0; j  heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Reset stack for PSE
        stack.length = 0;
        for (let j = cols - 1; j >= 0; j--) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute max area for this row
        for (let j = 0; j < cols; j++) {
            maxArea = Math.max(maxArea, heights[j] * (nse[j] - pse[j] - 1));
        }
    }

    return maxArea;
}

JavaScript 솔루션 (버전 2)

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (let i = 0; i < rows; ++i) {
        // Update heights
        for (let j = 0; j < cols; ++j) {
            heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
        }

        // Compute NSE
        const nse = new Array(cols).fill(cols);

        const stack = [];
        for (let j = 0; j < cols; ++j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute PSE
        const pse = new Array(cols).fill(-1);
        stack.length = 0;
        for (let j = cols - 1; j >= 0; --j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Calculate max area for this row
        for (let j = 0; j < cols; ++j) {
            maxArea = Math.max(maxArea, heights[j] * (nse[j] - pse[j] - 1));
        }
    }

    return maxArea;
}

핵심 요점

• 문제 축소: 2‑D 문제를 1‑D 문제(히스토그램)의 연속으로 보는 것이 강력한 사고 모델이다.
• 단조 스택: 이는 O(n) 시간에 “가장 가까운 작은” 또는 “가장 가까운 큰” 요소를 찾는 데 필수적이다.
• 공간‑시간 트레이드오프: 높이와 스택을 위해 O(n) 추가 공간을 사용함으로써 전체 시간 복잡도를 O(m × n) 로 만들 수 있으며, 이는 완전 탐색보다 훨씬 빠르다.

최종 생각

이 문제는 여러 단계의 논리를 결합하기 때문에 고급 기술 면접에서 필수적인 문제입니다. 실제 엔지니어링에서는 이러한 기술이 다음과 같이 사용됩니다:

• 컴퓨터 비전 – 객체 탐지를 위해.
• 데이터베이스 최적화 – 연속된 자유 공간 블록을 찾기 위해.
• UI 렌더링 – 레이아웃 엔진을 위해.

단조 스택을 마스터하면 훨씬 더 강력한 문제 해결사가 될 수 있습니다.