Maximal Rectangle - LeetCode

Problem

1. input: 1과 0으로 채워진 이중 배열 matrix
2. output: matrix의 1로만 이루어진 직사각형 중, 최대 넓이 리턴
   • rows == matrix.length
   • cols == matrix[i].length
   • 1 <= row, cols <= 200
   • matrix[i][j] is '0' or '1'.

Idea

직사각형을 만들기 위해선 내부의 모든 값들이 1이어야한다. 때문에 2차원의 matrix를 연속된 1의 갯수로 표현하여 1차원으로 만들 수 있다.

1차원의 배열에 대해서는 Monotonic 스택을 활용하여 O(1)로 최대 넓이를 구할 수 있다 → Sol1

Solution

1. Monotonic 스택

   • 각 행별로 각 열의 연속된 1의 갯수 계산 ex) 아래의 matrix의 경우 → [[3, 0, 2, 3, 2]. [2, 1, 1, 2, 1], [1, 0, 0, 1, 0]]

     

   • 위의 방법으로 만든 각 행에 대하여 Monotonic 스택으로 최대 넓이 갱신

   import java.util.*
   
   class Data(val idx: Int, val height: Int)
   class Solution {
       var maxArea = 0
       fun maximalRectangle(matrix: Array<CharArray>): Int {
           val heights = Array<Array<Int>>(matrix.size){Array(matrix[0].size){0}}
           // 연속되는 1의 개수 계산
           for (i in matrix.indices) {
               for (j in heights[0].indices) {
                   if (matrix[i][j] == '1') {
                       var acc = 1
                       var start = i + 1
                       while (start < heights.size && matrix[start][j] == '1') {
                           start++
                           acc++
                       }
                       heights[i][j] = acc
                   }
               }
           }
           for (height in heights) { // 한 행씩 최대넓이 계산
               largestRectangleArea(height)
           }
           return maxArea
       }
       fun largestRectangleArea(heights: Array<Int>): Int {
           val stack = LinkedList<Data>()
           for (i in heights.indices) { // 앞에서부터 하나씩
               var tmp = i // pop 대비 idx 저장
               while (stack.isNotEmpty() && heights[i] < stack.peekLast().height) { // 최상단 높이가 더 높은 경우
                   tmp = stack.peekLast().idx // 최상단 막대 idx 저장
                   maxArea = maxOf(maxArea, 
   										(i - stack.peekLast().idx) * stack.pollLast().height) // 최대 넓이 갱신 후 pop
               }
               stack.offerLast(Data(tmp, heights[i])) // pop한 막대의 idx로 삽입
           }
           // 스택에 남은 막대 처리
           while (stack.isNotEmpty()) {
               maxArea = maxOf(maxArea, (heights.size - stack.peekLast().idx) * stack.pollLast().height) // 최대 넓이 갱신 후 pop
           }
           return maxArea
       }
   }
   

   시간 복잡도: 배열 순회(연속된 1의 높이) X 배열 순회(최대 넓이) = n^2

   

Point

1. Monotonic Stack