LeetCode: 84. Largest Rectangle in Histogram

转载请注明, 原文地址:LeetCode: 84. Largest Rectangle in Histogram

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.

只在i比i+1高的时候 不断遍历之前的,宽度为1(自己本身)也遍历

    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty()) return 0;

        auto res=heights[0];
        for(auto i=1;i<heights.size();++i){
            auto tmp=(i+1==heights.size())?0:heights[i+1];
            if(heights[i]>tmp){

                auto min_height=heights[i];
                for(auto j=i;j>=0;--j){
                    min_height=min(heights[j],min_height);
                    auto value=min_height*(i-j+1);
                    res=max(value,res);
                }
            }
        }

        return res;
    }

Runtime: 16 ms, faster than 52.83%
Memory Usage: 9.9 MB, less than 97.14%

转载请注明:

转载自YuLai's Blog,原文地址:LeetCode: 84. Largest Rectangle in Histogram

http://xzh.i3geek.com

发表评论

发表回复

*

沙发空缺中,还不快抢~