Largest Rectangle in Histogram (C#)

 

너비가 1인 막대의 높이를 배열로 입력 받을 때, 가장 큰 사각형의 넓이를 구하는 문제입니다.

 

 

풀이 방법

특정 범위에서 크기가 가장 작은 막대를 찾은 후, (해당 범위의 길이 * 막대의 높이)가 우리가 구해야할 크기입니다.

이것을 모든 범위에서 해주면 되는데, 그렇게 되면 시간 초과가 발생하는 문제가 생깁니다.

 

이 문제를 해결하기 위해 Stack을 이용해줍니다.

가장 작은 수가 stack의 맨 위에 오도록 설계 해준 후, 탐색중인 범위의 넓이를 구해준다면 O(N)의 속도로 해결이 가능합니다.

 

 

Stack 풀이 전략

1. 반복문을 통해 0 ~ heights.Length-1 까지 Stack에 넣어줍니다. (Stack에는 범위 계산을 위해 Index를 넣어줍니다)

 

2. 이 때, 현재 Stack의 가장 위에 있는 수가 지금 넣으려는 높이보다 크다면, 필요가 없는 수(넓이는 작은 수를 기준으로 계산하기 때문) 이기 때문에 Pop을 통해 제거 합니다.

 

3. 2번을 현재 index의 높이보다 큰 값이 안나오거나 Stack이 비어있을 때 까지 반복합니다.

 

4. 결과적으로 Stack이 비어있거나, 현재 넣으려는 높이보다 작은 높이의 Index가 남아있게 됩니다.

index 5번을 넣을 때, 높이5, 6이 삭제 됨

 

5. 그럼 사각형의 범위는 Stack.Pop() ~ Stack.Peak()+1가 되며 넓이는 범위 * heights[Stack.Pop]가 됩니다.

 

6. 이렇게 찾은 넓이 중 가장 큰 값을 저장해줍니다.

 

7. 반복문을 종료한 이후에도 Stack에 남아있는 수가 있을 수 있습니다. 위 예시 사진에는 마지막에 Index 2(높이1)가 남아있을 것 입니다.

 

8. Stack에 남은 수는 해당 Index부터 끝까지의 범위 중 가장 작은 수 이기 때문에 다시 한번 넓이를 계산합니다.

 

9. 8번을 Stack이 비게 될 때까지 반복합니다.

 

 

정답 코드

public class Solution {
    public int LargestRectangleArea(int[] heights)
    {

        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        int n = heights.Length;

        for (int i = 0; i < n; i++)
        {
            while (stack.Count > 0 && heights[i] < heights[stack.Peek()])
            {
                int h = stack.Pop();
                int width;

                if (stack.Count == 0)
                    width = i;
                else
                    width = i - stack.Peek() - 1;

                int area = heights[h] * width;
                maxArea = Math.Max(maxArea, area);
            }
            stack.Push(i);
        }

        while (stack.Count > 0)
        {
            int h = stack.Pop();
            int width;

            if (stack.Count == 0)
                width = n;
            else
                width = n - stack.Peek() - 1;

            int area = heights[h] * width;
            maxArea = Math.Max(maxArea, area);

        }


        return maxArea;
    }
}