Largest Rectangle in Histogram - LeetCode

Problem

1. input: 히스토그램의 높이(정수)가 담긴 배열 heights
2. output: 이어진 히스토그램에서 만들 수 있는 직사각형 넓이의 최댓값 리턴

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

Idea

완전 탐색을 통해, 모든 막대에 대하여 좌,우 연속되는 자신 보다 높은 막대의 수를 구하면 해결은 할 수 있지만, 시간 초과에 걸릴 가능성이 크다 → Sol1

직사각형을 만들려면 연속된 막대들이 기준 높이의 막대보다 크거나 같아야 한다.

Monotonic 스택을 사용하여 오름 차순으로 스택을 유지하면 O(n)으로 최대 넓이를 구할 수 있다. ⇒ 스택을 오름차순으로 유지하면 i번째 막대의 높이로 i+1번째 막대와 직사각형을 만들 수 있음이 보장된다. → Sol2

Solution

1. 완전 탐색

   모든 막대에 대해 좌,우 탐색 → 연속되는 자신 보다 같거나 큰 막대의 갯수

   class Solution {
       fun largestRectangleArea(heights: IntArray): Int {
           var answer = 0
           for (i in heights.indices) {
               val height = heights[i]
               var area = -height
               if (answer >= height * heights.size) continue
               for (left in i downTo 0) {
                   if (heights[left] < height) break
                   area += height
               }
               for (right in i until heights.size) {
                   if (heights[right] < height) break
                   area += height
               }
               answer = maxOf(answer, area)
           }
           return answer
       }
   }
   

   시간 복잡도: 배열 탐색 X 배열 탐색 = n^2

   

2. Monotonic 스택

   스택의 막대들이 항상 오름차순이 되도록 유지

   오름차순이 아닌 막대가 삽입되어야 하는 경우, 해당 막대보다 큰 막대들을 모두 pop

   import java.util.*
   
   class Data(val idx: Int, val height: Int)
   class Solution {
       fun largestRectangleArea(heights: IntArray): Int {
           val stack = LinkedList<Data>()
           var maxArea = 0
           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) 
           }
           return maxArea
       }
   }
   

   시간 복잡도: 배열 탐색 + 배열 탐색 = n

   

Point

1. Monotonic Stack