求直方图的最大面积
使用栈结构来解决这个问题。始终保持栈内的数据为单增,如果不是,出栈并计算。
参考:
http://blog.csdn.net/doc_sgl/article/details/11805519
class Solution { public: int largestRectangleArea(vector<int> &height) { if(height.size() <= 0)return 0; height.push_back(-1); int max = 0x80000000; vector<int>stack; stack.clear(); stack.push_back(0); for(int i = 1;i < height.size();i++) { if(height[stack[stack.size()-1]] <= height[i])stack.push_back(i); else { while(stack.size() > 0 && height[stack[stack.size() - 1]] > height[i]) { int heighttmpi = stack[stack.size()-1]; stack.pop_back(); if(stack.size() == 0) { if(height[heighttmpi] * (i-0) > max)max = height[heighttmpi]<em>(i-0); } else { if(height[heighttmpi] * (i-stack[stack.size()-1]-1) > max)max = height[heighttmpi]</em>(i-stack[stack.size()-1]-1);</p> <pre><code> } } stack.push_back(i); } } return max; } </code></pre> <p>};