首页 » 编程之美 » 正文

[leetcode_84]Largest Rectangle in Histogram

求直方图的最大面积
使用栈结构来解决这个问题。始终保持栈内的数据为单增,如果不是,出栈并计算。
参考:
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) &gt; max)max = height[heighttmpi]<em>(i-0);
                    }
                    else {
                        if(height[heighttmpi] * (i-stack[stack.size()-1]-1) &gt; max)max = height[heighttmpi]</em>(i-stack[stack.size()-1]-1);</p>

<pre><code>                }
            }
            stack.push_back(i);
        }
    }
    return max;
}
</code></pre>

<p>};

发表评论