[LeetCode] Largest Rectangle in Histogram

문제

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

 

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

 

The largest rectangle is shown in the shaded area, which has area = 10 unit.

 

Example:

Input: [2,1,5,6,2,3] Output: 10

 

Approach

i번째 막대에서 가장 큰 직사각형을 만드려면 i번째 막대로부터 왼쪽으로 가장 멀리 떨어진 i번째 막대와 높이가 크거나 같은 막대의 왼쪽 막대(l),

그리고 i번째 막대로부트 오른쪽으로 가장 멀리 떨어진 i번째 막대와 높이가 크거나 같은 막대의 오른쪽 막대(r)를 찾은 다음,

(r-l-1)*(i번째 막대의 높이)를 계산하면 되고 이 값들 중 가장 큰 값이 답이된다.

이를 구현하기 위한 방법으로는 DP와 Stack을 활용하는 방법이 있다.

 

DP를 활용하는 방법은 각 i번째 막대의 왼쪽 오른쪽을 탐색하며 l과 r을 기록하는 배열을 저장하고

이 배열을 활용해 면적을 구한다.

 

Stack을 활용할 경우 왼쪽부터 막대의 높이를 stack에 push하며 stack.top()보다 현재 보고 있는 막대의 높이가 낮을 경우 stack에서 r과 l을 불러와 면적을 계산한다. (r은 현재 보고 있는 낮은 막대, 높이는 height[stack.top()], l은 stack.top() 바로 밑 index)

 

둘다 시간복잡도는 O(n)이고 DP를 활용한 쪽이 좀더 직관적이고 이해하기 쉽다.

Discuss를 참조하여 풀었다.

 

Code

DP: https://github.com/chi3236/algorithm/blob/master/LeetCode_LargestRectangleInHistogram_DP.cpp

chi3236/algorithm

Stack: https://github.com/chi3236/algorithm/blob/master/LeetCode_LargestRectangleInHistogram_Stack.cpp

chi3236/algorithm