Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] Maximal Rectangle

[Maximal Rectangle]

• Prefix sum + Monotone stack
• 누적합 구해놓고 각 행마다 [히스토그램에서 가장 큰 직사각형]
• 시간이 너무 늦어서 상세한 풀이는 나중에,,, 😢

Solution. $O(NM)$

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n, m = len(matrix), len(matrix[0])

        dp = [[*map(int, r)]+[-1] for r in matrix]
        for i in range(1, n):
            for j in range(m):
                if dp[i][j]: dp[i][j] += dp[i-1][j]

        mx = 0
        for row in dp:
            stack = [-1]

            for i in range(m+1):
                while row[i] < row[stack[-1]]:
                    sq = row[stack.pop()] * (i-1-stack[-1])
                    if mx < sq: mx = sq
                stack.append(i)

        return mx

---

Memo

• 풀이 작성
• DP 코드 찾아보기
• 나름대로 다른 접근 해보기