LeetCode Online Judge 제목 C# 연습 - 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.
For example,Given height = [2,1,5,6,2,3],return 10.

 1         public static int LargestRectangleinHistogramOpt(List<int> height)

 2         {

 3             if (height.Count == 0)

 4                 return 0;

 5             if (height.Count == 1)

 6                 return height[0];

 7 

 8             int[] Base = new int[height.Count];

 9             Stack<int> s = new Stack<int>();

10             int MaxArea = 0;

11 

12             //Calculate the base from left to right

13             for (int i = 0; i < height.Count; i++)

14             {

15                 while(s.Count > 0 && height[i] < height[s.Peek()])

16                 {

17                     Base[s.Peek()] = i - s.Peek();

18                     s.Pop();

19                 }

20 

21                 s.Push(i);

22             }

23             while (s.Count > 0)

24             {

25                 Base[s.Peek()] = height.Count - s.Peek();

26                 s.Pop();

27             }

28 

29             //Add base from right to left

30             for (int i = height.Count - 1; i >= 0; i--)

31             {

32                 while (s.Count > 0 && height[i] < height[s.Peek()])

33                 {

34                     Base[s.Peek()] += s.Peek() - i - 1;

35                     s.Pop();

36                 }

37 

38                 s.Push(i);

39             }

40             while (s.Count > 0)

41             {

42                 Base[s.Peek()] += s.Peek();

43                 s.Pop();

44             }

45 

46             //Find the MaxArea

47             for (int i = 0; i < height.Count; i++)

48             {

49                 MaxArea = Math.Max(MaxArea, Base[i] * height[i]);

50             }

51 

52             return MaxArea;

53 

54         }

코드 분석:
위 코드의 시간 복잡도는 O(n)입니다.좀 이상적인 방법일 거예요.
　　1. 왼쪽에서 오른쪽으로 대응하는 높이의 오른쪽 밑바닥의 길이를 계산하다.
　　2. 오른쪽에서 왼쪽으로 대응하는 높이 왼쪽 땅의 길이를 더해라.
　　3. 밑바닥을 통과하다×높음, 최대 면적 계산
펴기 1.
Stack 도움말을 사용하여 계산합니다.
예를 들어 [2,1,5,6,2,3]
　　Base[0,0,0,0,0,0]   Stack[ )
　　　　1.i = 0 Base[0,0,0,0,0,0] Stack[0,)
　　　　2.i = 1 하향, Base[1,0,0,0,0,0,0] Stack[0,1,)
　　　　3.i = 2 상승연, Base[1,0,0,0,0,0,0] Stack[1,2)
　　　　4.i = 3 상승연, Base[1,0,0,0,0,0,0] Stack[1,2,3)
　　　　5.i = 4 하강연, Base[1,0,2,1,0,0] Satck[1,2,3,4)
　　　　6.i = 5 상승연, Base[1,0,2,1,0,0] Stack[1,4,5)
　　　　7.베이스[1,5,2,1,2,1]Stack[1,4,5)