85. Maximal Rectangle

어제 풀었던 문제와 유사한 문제입니다.

 

https://ggodong.tistory.com/226

84. Largest Rectangle in Histogram

 

그러니 간단히 설명을 하고 마무리 짓도록하겠습니다.

---

우선 스택을 사용한다는 점에서는 똑같은 문제입니다만... 2차원이죠 그쵸?

 

그렇다면 저희는 이 2차원을 커스터마이징을 해야한다는 소리인데, 어떻게 할 수 있을까요?

 

2차원에 표시되어 있는 1을 높이로 바꿀 수 있지 않을까요??

 

예를 들어봅시다.

 

[
	[1, 1, 1, 1],
    [0, 1, 1, 0],
    [1, 1, 1, 0],
    [0, 0, 1, 1]
]

요런 2차원 배열이 있다고 했을 때 저희는 이 배열을 높이 기준으로 표시를 할 수 있습니다. 저는 i행의 제일 마지막 행 0번행을 땅바닥으로 보도록 하겠습니다.

이런 식으로 보시면 됩니당

[
	[1, 3, 4, 1],
    [0, 2, 3, 0],
    [1, 1, 2, 0],
    [0, 0, 1, 1]
]

요렇게 되겠죠?

 

이러면 문제를 해결할 수 있지 않을까요..?

 

왜냐면 각각의 한 행이 결국엔 히스토그램을 완성시켜주는 거니까요 !

이게 각각 한 행에 있다고 생각하자

그럼 앞 전에 풀었던 문제와 완전 똑같은 문제입니다. 다만, 각 행마다 확인을 해야하는 점만 다를 뿐이죠 !

 

코드 들어갑니다잉

 

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if matrix == []: return 0
        else:
            mat = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
            for i in range(len(matrix)):
                for j in range(len(matrix[i])):
                    if matrix[i][j] == "1":
                        hei = 0
                        idx = i
                        while idx < len(matrix):
                            if matrix[idx][j] == "1":
                                hei += 1
                            else: break
                            idx += 1
                        mat[i][j] = hei
            result = 0
            for i in range(len(mat)):
                stack = [[0, mat[i][0]]]
                for j in range(1, len(mat[i])):
                    idx = j
                    while stack != [] and stack[-1][1] > mat[i][j]:
                        val = stack[-1][1] * (j - stack[-1][0])
                        if result < val: result = val
                        idx = stack.pop()[0]
                    stack.append([idx, mat[i][j]])
                while stack != []:
                    val = stack[-1][1] * (len(mat[i]) - stack[-1][0])
                    if result < val: result = val
                    stack.pop()
            return result

완전 똑같습니다. 완전 !

 

for문 한 번 더 돈다는거 빼고요.

---

이상 85. Maximal Rectangle였습니다. ^_^