在某篇博客见到的Largest Rectangle in Histogram的题目,感觉蛮好玩的,于是想呀想呀,怎么求解呢?
还是先把题目贴上来吧
题目写的很直观,就是找直方图的最大矩形面积,不知道是受之前的trie tree影响怎么的,感觉树这玩意还真有用,于是就思考呀,还真别说,真想出一种方式,好吧,其实是入了一个大坑,也无妨,记录下来,好歹也是思路历程.....
大概思路这样的:
每次寻找直方图的最小值,记录此时以该最小值,和以其为高度的矩形面积,再将直方图以该最小值为界限,将直方图分成若干份,按照同样思路对每个子直方图继续求解,这样如果把每个直方图作为节点的话,其实也形成了一棵树,不过这树没啥价值,因为本题并不关心得到最大矩形的路径,只要求面积即可,是时候献丑了,代码贴上:
#include <vector>
#include <list>
#include <iostream>
#include <stack>
using namespace std;
class LRTreeNode
{
private:
int getMin()
{
if (right-left == 0)
{
return 0;
}
int min = (*heights)[left];
for (int i=left;i<right;i++)
{
min = (*heights)[i] > min ? min : (*heights)[i];
}
return min;
}
void getMaxArea()
{
maxArea = bottom*(right-left);
}
public:
int left, right;
int bottom;
int min;
int maxArea;
static vector<int>* heights;
vector<LRTreeNode*> lrnv;
LRTreeNode(int bottom,int left,int right)
{
this->left = left;
this->right = right;
this->bottom=getMin()+bottom;
this->min = getMin();
getMaxArea();
}
vector<LRTreeNode*>* genChildren()
{
int left2=left, right2=left;
for (int i = left; i < right; i++)
{
(*heights)[i] -= min; if ((*heights)[i] == 0 )
{
if (right2-left2 != 0)
{
lrnv.push_back(new LRTreeNode(bottom,left2,right2));
}
left2 = i+1;
right2 = i+1;
}
else
{
right2++;
}
}
if (right2 - left2 != 0)
{
lrnv.push_back(new LRTreeNode(bottom, left2, right2));
}
return &lrnv;
}
};
vector<int>* LRTreeNode::heights = NULL;
class LRTree
{
private:
LRTreeNode root;
public:
LRTree(vector<int>& heights) :root(0,0,heights.size())
{ }
int getMaxArea()
{
int max = root.maxArea;
list<LRTreeNode*> st;
vector<LRTreeNode*>* t = root.genChildren();
LRTreeNode* stt;
for (int i = 0; i < t->size(); i++)
{
st.push_back((*t)[i]);
max = max >(*t)[i]->maxArea ? max : (*t)[i]->maxArea;
}
while (st.empty() == false)
{
stt = st.back();
t = stt->genChildren();
st.pop_back();
for (int i = 0; i < t->size(); i++)
{
st.push_back((*t)[i]);
max = max > (*t)[i]->maxArea ? max : (*t)[i]->maxArea;
}
delete stt;
}
return max;
}
}; class Solution {
public:
int largestRectangleArea(vector<int>& heights);
};
int Solution::largestRectangleArea(vector<int>& heights)
{
LRTreeNode::heights = &heights;
LRTree t(heights);
return t.getMaxArea();
} int main()
{
vector<int> t = {1,2,3,4,5};
Solution s;
cout << s.largestRectangleArea(t);
return 0;
}
代码里面有几个值得注意的问题:
1.按照之前所说的思路,每个节点都得存储一个子直方图,这样并非最好方法,试想如果直方图为n,依次增加,则空间复杂度为O(n^2),故采用了所有节点共用一个直方图,每个节点存储左右界限即可,也就是LRTreeNode的left,right;
2.在每次的子直方图中都减去了底部部分,所以最终的直方图数据会被变化。
该种方法虽然采用了分治的思想,但其本质其实是遍历了所有的可能的矩形,其实效果并不好,由于最小值的多次寻找增加了复杂度,但作为思路历程,还是一并记录。