leetcode84

 1 public class Solution
 2     {
 3         public int LargestRectangleArea(int[] hist)
 4         {
 5             // The main function to find the  
 6             // maximum rectangular area under  
 7             // given histogram with n bars  
 8             int n = hist.Length;
 9             // Create an empty stack. The stack  
10             // holds indexes of hist[] array  
11             // The bars stored in stack are always  
12             // in increasing order of their heights.  
13             Stack<int> s = new Stack<int>();
14 
15             int max_area = 0; // Initialize max area 
16             int tp; // To store top of stack 
17             int area_with_top; // To store area with top  
18                                // bar as the smallest bar 
19 
20             // Run through all bars of 
21             // given histogram  
22             int i = 0;
23             while (i < n)
24             {
25                 // If this bar is higher than the  
26                 // bar on top stack, push it to stack  
27                 if (s.Count == 0 || hist[s.Peek()] <= hist[i])
28                 {
29                     s.Push(i++);
30                 }
31 
32                 // If this bar is lower than top of stack, 
33                 // then calculate area of rectangle with  
34                 // stack top as the smallest (or minimum   
35                 // height) bar. 'i' is 'right index' for  
36                 // the top and element before top in stack 
37                 // is 'left index'  
38                 else
39                 {
40                     tp = s.Peek(); // store the top index 
41                     s.Pop(); // pop the top 
42 
43                     // Calculate the area with hist[tp] 
44                     // stack as smallest bar  
45                     area_with_top = hist[tp] *
46                                    (s.Count == 0 ? i : i - s.Peek() - 1);
47 
48                     // update max area, if needed  
49                     if (max_area < area_with_top)
50                     {
51                         max_area = area_with_top;
52                     }
53                 }
54             }
55 
56             // Now pop the remaining bars from  
57             // stack and calculate area with every  
58             // popped bar as the smallest bar  
59             while (s.Count > 0)
60             {
61                 tp = s.Peek();
62                 s.Pop();
63                 area_with_top = hist[tp] *
64                                (s.Count == 0 ? i : i - s.Peek() - 1);
65 
66                 if (max_area < area_with_top)
67                 {
68                     max_area = area_with_top;
69                 }
70             }
71 
72             return max_area;
73         }
74     }

 1 class Solution:
 2     def largestRectangleArea(self, heights: 'List[int]') -> int:
 3         heights.append(0)#默认最后补充一个0，方便统一处理
 4         n = len(heights)
 5         s = []
 6         max_area = 0#最大面积
 7         tp = 0#栈顶索引
 8         area_with_top = 0#临时面积
 9         i = 0
10         while i < n:
11             if len(s) == 0 or heights[s[-1]] <= heights[i]:
12                 s.append(i)#栈内记录的是高度递增的索引
13                 i += 1
14             else:#遇到了高度比当前栈顶元素低的元素时，
15                 tp = s.pop(-1)#清算栈内的元素的高度
16                 if len(s) == 0:
17                     area_with_top = heights[tp] * i#栈内没有元素，则宽度是i
18                 else:#高度是栈顶元素，宽度是i - 1 - 前一个栈顶元素的索引
19                     area_with_top = heights[tp] * (i - s[-1] - 1)
20                 max_area = max(max_area,area_with_top)#更新最大值
21         # while len(s) > 0:#处理栈内剩余元素，处理流程和遇到一个
22         #     tp = s.pop(-1)
23         #     if len(s) == 0:
24         #         area_with_top = heights[tp] * i
25         #     else:
26         #         area_with_top = heights[tp] * (i - s[-1] - 1)
27         #     max_area = max(max_area,area_with_top)
28         return max_area