注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex84 Largest Rectangle in Histogram  

2015-05-26 22:54:42|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这个题目的方法很巧妙,我表示我想不到,不过这个算法确实很有用,o(n)的,在统计里面应该很常用。

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.

ex84 Largest Rectangle in Histogram - HT - HT·生活

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

ex84 Largest Rectangle in Histogram - HT - HT·生活

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.


简单描述一下,从第一个元素往栈里面放,当遇到一个元素的比栈顶的元素小的时候开始弹栈,每弹一次,算一次面积,求最大的,最后直到遇到比自己小的元素。这样的做法就是让栈里面是按照序列上升的方式存储元素的。参考中第一个作者画了几张比较直观的图,就不盗图了。对了,暴力搜索是n^2的复杂度。

/*
* 好吧!我表示线性算法我是想不出来,只能用暴力搜索的方法
*/
class Solution {
public:
int largestRectangleArea(vector<int>& height) {

return traverse(height);
}
int traverse(vector<int>& height)
{
//使用栈 线性算法
height.push_back(0);//在height后面添加一个0元素,作为边界判定
stack<int> myStack;
int i = 0;
int maxArea = 0;
int len = height.size();
while (i < len)
{
if (myStack.empty() || (height[myStack.top()] <= height[i]))
{
//如果第一次入栈,或者后面弹栈后的top小于等于i指向元素
//那么就不必再弹栈了
myStack.push(i);
i++;
}
else
{
//开始把较大元素弹出来
int index = myStack.top();
myStack.pop(); //取出栈顶
//计算面积
int width = 0;
if (myStack.empty())
{
width = i;
}
else
{
width = i - myStack.top()-1;
}
maxArea = myMax(maxArea,height[index]*width);
}
}
return maxArea;

}
int myMax(int a,int b)
{
return a > b ? a : b;
}
int traverse1(vector<int>& height)
{
//暴力搜索的方法
//超时
int len = height.size();
int i, j;
int largestAera = 0;
int area = 0;
for (i = 0; i < len; i++)
{
area = 0;
int low = height[i];
for (j = i; j < len; j++)
{
if (height[j] < low) low = height[j];

area = (j - i + 1)*low;
if (area>largestAera) largestAera = area;
}
}
return largestAera;
}
};






参考
http://blog.csdn.net/doc_sgl/article/details/11805519
http://www.cnblogs.com/avril/archive/2013/08/24/3278873.html
  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017