LeetCord - 84. Largest Rectangle in Histogram

주어진 배열 heights는 히스토그램의 막대 높이를 나타내는 정수들로 구성되어 있습니다.

각 막대의 너비는 1로 가정하고, 히스토그램에서 가장 큰 직사각형의 넓이를 반환하는 문제 입니다.

 

https://www.algotree.org/algorithms/stack_based/largest_rectangle_in_histogram/

Finding the Largest Area Rectangle In A Histogram :: AlgoTree

미사여구 문제 풀이 작성하다 이 사이트를 보고 현타와서 그냥 주소 링크를 겁니다.

지금 까지 본 문제 풀이중 가장 이해하기 쉽게 설명해주는 것 같습니다.

 

 

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

        int len = heights.Length;
        int max = 0;

        Stack<int> height = new Stack<int>();
        Stack<int> start = new Stack<int>();

        int pot = 0;

        for (int i = 0; i < len; i++)
        {
            if (height.Count == 0 || height.Peek() <= heights[i])
            {
                height.Push(heights[i]);
                start.Push(i);
            }
            else
            {
                while (height.Count > 0 && height.Peek() > heights[i])
                {
                    int h = height.Pop();
                    pot = start.Pop();
                    max = Math.Max(max, h * (i - pot));
                }
                height.Push(heights[i]);
                start.Push(pot);
            }

        }

        while (height.Count != 0)
        {
            int h = height.Pop();
            int idx = start.Pop();

            max = Math.Max(max, h * (len - idx));
        }

        return max;
    }
}