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         }