LC85: Maximal Rectangle

작성일

https://leetcode.com/problems/maximal-rectangle/

  • 앞선 풀었던 LC84를 이용하는 문제이다.
  • DP로 현재 row에서 위쪽으로 만들 수 있는 histogram을 계산하고, 이걸로 최대 사각형 문제를 풀면 된다.
  • 모든 row에 대해서 최대 사각형을 찾으면, 이게 행렬 전체의 최대 사각형이 된다.
  • c++로는 한번 풀었으니, 파이썬으로 풀어봤는데.. 코드가 진짜 짧아진다. 특히나 14번 줄 같은 경우는 C++로는 4줄짜리인데 한줄로 끝난다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def largestHistogram(self, heights):
        st, ans = [-1], 0
        heights.append(0)
        for i, h in enumerate(heights):
            while len(st) > 1 and heights[st[-1]] > heights[i]:
                ans = max(ans, heights[st.pop()] * (i - st[-1] -1))
            st.append(i)
        return ans
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        row, w, ans = [0] * len(matrix[0]), len(matrix[0]), 0
        for cur in matrix:
            row = [ row[i]+1 if cur[i] == "1" else 0 for i in range(w) ]
            ans = max(ans, self.largestHistogram(row))
        return ans