C# LeetCode - 80 Largest Rectangle in Histogram 풀이

출처: 84. Largest Rectangle in Histogram (tistory.com)

84. Largest Rectangle in Histogram

 

 

개인적으로 이 문제에 대해 질 좋은 코드와 예시가 적혀있어서 이 블로그의 코드를 참고했습니다.

 

문제: Largest Rectangle in Histogram - LeetCode

Largest Rectangle in Histogram - LeetCode

 

전체 코드

for(int i = 0; i < heights.Length; i++)
{
idx = i - 1;

while(idx > -1 && heights[idx] >= heights[i])
{
max = Math.Max(max, heights[idx] * (i - lastSmallIdx[idx] - 1));
idx = lastSmallIdx[idx];
}
lastSmallIdx[i] = idx;
}
idx = heights.Length - 1;

 

우선 이 부분의 코드만 잘 이해 한다면 전체적인 코드의 이해가 쉬울 것이라고 판단하여 설명을 드립니다.

 

for문: 배열의 길이만큼 반복문을 돕니다.

idx = i - 1을 하는 이유는 현재의 while문의 heights[idx] >= heights[i]을 때문입니다.

즉, i를 1 감소시켜 인덱스의 바로 이전 값과 현재 값을 비교해야 하기 때문입니다.

 

우선 첫번 째로 i가 0일때는 while문의 조건을 만족하지 못하여 idx에 -1값이 들어간 후 배열[0]번째에 -1이 들어가게 됩니다. 우선 배열의 height값이 2, 3, 4, 1이 들어왔다고 가정하고 쭉 진행해보면 

[0] = -1

[1] = 0

[2] = 1

까지 들어오게 됩니다. 왜냐하면 i가 3일 때는 height값 4와 1이 비교가 되는데 while문의 조건을 모두 만족하기 때문입니다. 이제 while문이 실행되면서 현재 height[idx] 즉, 4이며 현재의 i인 3에 순서가 저장된 배열의 idx = 2를 넣은 1에 -1을 한 값을 곱하게 됩니다. 최종적으로 4 * (3 - 1 - 1) = 4 * 1 이됩니다. 이 말은 높이가 4인 사각형의 넓이가 하나만 가능하다는 것입니다.

이렇게 계속 진행하게 된다면 3 * 2, 2 * 3이 됩니다. 쉽게 말하자면 높이가 4인 사각형이 하나만 있을때는 최대 값 4, 높이가 3, 4인 사각형이 있을 때는 3높이가 두번 겹치니깐 3 * 2 = 6의 최대 값, 높이가 2, 3, 4인 직사각형이 있을 때는 높이가 2인 사각형이 3번 겹칠 수 있기 때문에 2 * 3 = 6의 최대 값을 가지게 됩니다.

 

여기까지 이해가 되셨다면 아래의 코드는 역방향으로 다시 탐색하는 부분이기 때문에 이해에 도움이 될거라 생각합니다.

그렇게 양방향으로 넓이를 탐색해 최대 값을 갱신하여 찾아내게 되어 나온 답은 6입니다.

 

이 문제를 풀다보면 시간초과가 많이 나올텐데 스택과 양방향 탐색등의 기술을 이용하면 해결이 가능합니다.