首页 > 其他 > 详细

[LeetCode] Largest Rectangle in Histogram

时间:2014-06-08 21:24:27      阅读:405      评论:0      收藏:0      [点我收藏+]

第一种方法,暴力求解,从当前向左右两个方向扫描比自己小的,然后计算面积,时间复杂度O(n^2)code如下,但是在LeetCode上回超时。

bubuko.com,布布扣
 1 class Solution {
 2 public:
 3     int largestRectangleArea(vector<int> &height) {
 4         
 5         int size = height.size();
 6         int left = 0, right = 0, area = 0;
 7         
 8         for(int i = 0; i < size; i++)
 9         {
10             int j;
11             for( j = i-1; j>= 0;j--)
12             {
13                 if(height[j] <height[i])
14                 {
15                     left = j;
16                     break;
17                 }
18             }
19             
20             for(j = i+1; j<size; j++)
21             {
22                 if(height[j] <height[i])
23                 {
24                     right = j;
25                     break;
26                 }
27             }
28             
29             area = max(area, height[i] * (right - left -1));
30         }
31         
32         return area;
33         
34     }
35 };
bubuko.com,布布扣

第二种方法,对于每一个height[i],第一种方法用暴力查找的方法找它的左右边界,我们可以用一个stack来实现其左右边界的查找。我们维持一个递增的栈,由于是递增的,后压入栈的都比前面的大,所以其左边界就确定了,我们要做的是找右边界。当某一个height[j]小于当前栈顶元素时,就找到了右边界,则将计算以当前栈顶元素计算为高得面积;如果下一个栈顶元素还是大于height[j],则仍要计算面积,以此类推,知道最后,我们一下图举例。

对原有的height在末尾压入0.

初始,stack为空,

i = 0, push idx=0 into stack;

i = 1, height[1] = 7 > height[stack.top()] = 2, push idx=1 into stack;

i = 2, height[2] = 5 < height[stack.top()] = 7,pop idx=2 from stack, calc area = (i-stack.top()-1)*height[idx] = (2-0-1)*7=7;

     height[2] = 5 > height[stack.top()] = 2, stop to calc area and push 5 into stack.

i = 3, height[3] = 6 > height[stack.top()] = 5, push idx = 3 into stack;

i = 4, height[4] = 4 < height[stack.top()] = 6, pop idx = 3 from stack, calc area = (i-stack.top()-1)*height[idx]= (4-2-1)*6=6,

   height[4] = 4 < height[stack.top()] = 5, pop idx =2 from stack, calc area =(i-stack.top()-1)*height[idx]=(4-0-1)*5=15,

   height[4] = 4 > height[stack.top()] = 2, push idx= 4 into stack;

i = 5 height[5] = 0 < height[stack.top()] = 2, pop idx =0 form stack, calc area = i*height[idx]= 5 * 2 = 10;

所以最大面积为15.

 

 

bubuko.com,布布扣

 

 

bubuko.com,布布扣
 1 class Solution {
 2 public:
 3     int largestRectangleArea(vector<int> &height) {
 4       
 5         //add 0 to the end
 6         height.push_back(0);
 7         
 8         int size = height.size(); //this new_size is 1 + old_size
 9         stack<int> st;
10         
11         int max_area = 0;
12         
13 
14         
15         for(int i = 0; i< size; )
16         {
17             if(st.empty() || height[i] > height[st.top()])
18             {
19                 st.push(i);
20                 i++;
21             }
22             else
23             {
24                 //st must be not empty here
25                 // i can‘t ++; handle many times perhaps
26                 
27                 int idx = st.top();
28                 st.pop();
29                 
30                 int area;
31                 
32                 if(st.empty())
33                 {
34                     area = height[idx] * i;
35                 }
36                 else
37                 {
38                     area = height[idx] * (i-st.top()-1);
39                 }
40                 
41                 max_area = max(max_area, area);
42 
43             }
44         }
45         return max_area;
46     }
47 };
48 f
bubuko.com,布布扣

 

[LeetCode] Largest Rectangle in Histogram,布布扣,bubuko.com

[LeetCode] Largest Rectangle in Histogram

原文:http://www.cnblogs.com/diegodu/p/3775782.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!