在某篇博客见到的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.在每次的子直方图中都减去了底部部分，所以最终的直方图数据会被变化。
该种方法虽然采用了分治的思想，但其本质其实是遍历了所有的可能的矩形，其实效果并不好，由于最小值的多次寻找增加了复杂度，但作为思路历程，还是一并记录。