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.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]
.
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
.
思路:
暂时只想到了一个最容易想到的思路,对于每一个直方图,要么他自己是目标矩阵,要么和周围的直方图合并组成目标矩阵,那么对于每一个直方图,试图找到所有的合适的方法即可。
#include <iostream> #include <vector> #include <stack> #include <limits> using namespace std; int Longestest_rectangle(vector<int>& vec) { int i,j; int max=0; int hight; int tmp; for(i=0;i<vec.size();i++) { hight = numeric_limits<int>::max(); for(j=i;j<vec.size();j++) { if(hight > vec[j]) hight = vec[j]; max = max>(j-i+1)*hight?max:(j-i+1)*hight; } } return max; } int main() { int array[]={2,1,5,6,2,3}; vector<int> vec(array,array+sizeof(array)/sizeof(int)); cout<<Longestest_rectangle(vec)<<endl; return 0; }
LeetCode|Largest Rectangle in Histogram
原文:http://blog.csdn.net/yusiguyuan/article/details/44649993