public class Solution

     {

         public int LargestRectangleArea(int[] hist)

         {

             // The main function to find the

             // maximum rectangular area under

             // given histogram with n bars

             int n = hist.Length;

             // Create an empty stack. The stack

             // holds indexes of hist[] array

             // The bars stored in stack are always

             // in increasing order of their heights.

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

             int max_area = ; // Initialize max area

             int tp; // To store top of stack

             int area_with_top; // To store area with top

                                // bar as the smallest bar 

             // Run through all bars of

             // given histogram

             int i = ;

             while (i < n)

             {

                 // If this bar is higher than the

                 // bar on top stack, push it to stack

                 if (s.Count ==  || hist[s.Peek()] <= hist[i])

                 {

                     s.Push(i++);

                 }

                 // If this bar is lower than top of stack,

                 // then calculate area of rectangle with

                 // stack top as the smallest (or minimum

                 // height) bar. 'i' is 'right index' for

                 // the top and element before top in stack

                 // is 'left index'

                 else

                 {

                     tp = s.Peek(); // store the top index

                     s.Pop(); // pop the top 

                     // Calculate the area with hist[tp]

                     // stack as smallest bar

                     area_with_top = hist[tp] *

                                    (s.Count ==  ? i : i - s.Peek() - );

                     // update max area, if needed

                     if (max_area < area_with_top)

                     {

                         max_area = area_with_top;

                     }

                 }

             }

             // Now pop the remaining bars from

             // stack and calculate area with every

             // popped bar as the smallest bar

             while (s.Count > )

             {

                 tp = s.Peek();

                 s.Pop();

                 area_with_top = hist[tp] *

                                (s.Count ==  ? i : i - s.Peek() - );

                 if (max_area < area_with_top)

                 {

                     max_area = area_with_top;

                 }

             }

             return max_area;

         }

     }

 class Solution:

     def largestRectangleArea(self, heights: 'List[int]') -> int:

         heights.append(0)#默认最后补充一个0，方便统一处理

         n = len(heights)

         s = []

         max_area = 0#最大面积

         tp = 0#栈顶索引

         area_with_top = 0#临时面积

         i = 0

         while i < n:

             if len(s) == 0 or heights[s[-1]] <= heights[i]:

                 s.append(i)#栈内记录的是高度递增的索引

                 i += 1

             else:#遇到了高度比当前栈顶元素低的元素时，

                 tp = s.pop(-1)#清算栈内的元素的高度

                 if len(s) == 0:

                     area_with_top = heights[tp] * i#栈内没有元素，则宽度是i

                 else:#高度是栈顶元素，宽度是i - 1 - 前一个栈顶元素的索引

                     area_with_top = heights[tp] * (i - s[-1] - 1)

                 max_area = max(max_area,area_with_top)#更新最大值

         # while len(s) > 0:#处理栈内剩余元素，处理流程和遇到一个

         #     tp = s.pop(-1)

         #     if len(s) == 0:

         #         area_with_top = heights[tp] * i

         #     else:

         #         area_with_top = heights[tp] * (i - s[-1] - 1)

         #     max_area = max(max_area,area_with_top)

         return max_area