<Hard> Largest Rectangle in Histogram (LeetCode : C#)

https://leetcode.com/problems/largest-rectangle-in-histogram/

📕 문제 설명

히스토그램 막대의 높이를 나타내는 정수 배열이 주어질 때 히스토그램에서 가장 큰 직사각형의 영역 반환하기 (막대 너비는 1임)

• Input
  막대 높이 나타내는 정수 배열
• Output
  가장 큰 직사각형의 영역

예제

실패 (왜인지 의문..)

단순 divide and conquer 식으로 풀었는데 모두 같은 값인 경우의 테케가 통과가 되지 않았다. 그래서 해당 부분 추가로 처리했는데.. 마지막 테스트 케이스 걸린다. 이거는 근데 custom test case 돌릴 때 따로 에러 처리는 안되는데 왜일까 싶다.

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        if (heights.Count() == 0) return 0;
        HashSet<int> set = new HashSet<int>(heights);
        if (set.Count == 1) return (heights[0] * heights.Count());
        return CalculateArea(heights, 0, heights.Length - 1);
    }

    public int CalculateArea(int[] heights, int start, int end)
    {
        if (start > end)
        {
            return 0;
        }

        int minIndex = start;
        for (int i = start; i <= end; i++)
        {
            // 높이 최소 갱신
            if (heights[minIndex] > heights[i])
            {
                minIndex = i;
            }
        }

        int leftArea = CalculateArea(heights, start, minIndex - 1);
        int rightArea = CalculateArea(heights, minIndex + 1, end);

        return  Math.Max(heights[minIndex] * (end - start + 1), Math.Max(leftArea, rightArea));
    } 
}

풀이

직사각형을 하나하나 추가해나간다고 생각했을 때 크게 현재 추가되는 높이가 이전보다 큰 경우랑 작은 경우로 나누어 생각해볼 수 있다. 이전보다 작은 경우에는 현재 높이가 큰 것들 기준으로 max값을 계산한다. 큰게 들어오면 다음에 더 큰게 들어올 때 까지 계속 stack에 쌓아나간다. 그리고 마지막에 더 작아서 남아있던 height들 기준으로 가로가 킨 케이스를 고려하기 위해 계산해준다. (stack에는 index들을 저장해둔다.)

정리하면,

1. 현재 들어올 높이가 이전보다 큰 경우
   ex) 2, 5, 6, (8)
   8이 새로 들어오면 stack에 쌓는다.
   stack 상황 : [2, 5, 6, 8]

2. 현재 들어올 높이가 이전보다 작은 경우
   ex) 2, 5, 6, (2)
   여기 2가 새로 들어오면 현재 가장 큰 영역을 담당하는 5,6에 따로 영향을 주지 않는다. 따라서, 현재 들어온 값을 기준으로 앞에 더 큰 높이를 가진 부분의 영역을 계산하여 max를 갱신한다.

3. 마지막 index
   ex) 2, 5, 6, 2, 2, 2, 2, 2, 2 .. 2
   다음과 같이 더 낮은 높이지만 길게 늘어뜨려있으면 오히려 큰 영역을 만들 수 있다. 이 부분을 마지막 index를 보게되면 계산해서 현재 max에 저장된 값과 비교해준다.

while 문 안이 동작하는 방식은 다음과 같다.
ex) 2, 1, 5, 6, 2, 3

(stack에 예시로 알아보기 쉽게 value를 적었는데 실제로 해당 value에 매칭되는 index를 저장한다고 보면 된다.)

1) 2가 쌓여있고 1이 들어온 경우
-> 현재 1이 더 짧기 때문에 본인 앞 기준 더 높이가 긴 영역 계산 후 max update
처리 후 stack : [1]

2) 1, 5, 6이 쌓인 상태로 2가 들어오는 경우
-> 현재 2가 더 짧기 때문에 본인 앞 기준 더 높이가 긴 영역 계산 후 max update
처리후 stack [1, 2]

3) 마지막 index stack에 들어온 후
-> 마지막 index에서는 height를 0으로 잡고 앞에 남은 것들을 쭉 보게된다.
현재 stack이 [1, 2, 3] 이 되어있는 상태인데 currHeight * (i - 1 - prevIndex) 값은 다음과 같이 업데이트 된다.

currentHeight = 3, prevIndex = 5일 때 계산된 넓이 = 3

currentHeight = 2, prevIndex = 4일 때 계산된 넓이 = 2 * 2

currentHeight = 1, prevIndex = 1일 때 계산된 넓이 = 1 * 5

이게 그림으로 보면 더 이해가 쉬울텐데 현재 보는 높이 (즉, 마지막 값보다 짧은 케이스들)에다가 마지막 값에서 얼만큼 떨어진지를 곱하면 영역이 계산되는 구조

public class Solution {
    public int LargestRectangleArea(int[] heights) {
       int n = heights.Length, max = 0;
       Stack stack = new Stack<int>();
       
       for(int i = 0; i <= n; i++)
       {
            var height = i < n ? heights[i] : 0;
            // 현재거 기준보다 앞에 큰거 있는 경우 
            while(stack.Count != 0 && heights[stack.Peek()] > height) 
            {
                var currHeight = heights[stack.Pop()];
                var prevIndex = stack.Count == 0 ? -1 : stack.Peek();
                max = Math.Max(max, currHeight * (i - 1 - prevIndex));
            }
            stack.Push(i);
       }
        
        return max;
    }
}

결과