>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

leetcode刷题 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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

 

The largest rectangle is shown in the shaded area, which has area = 10 unit.

 

For example,
Given height = [2,1,5,6,2,3],
return 10.

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        vector<int> s;
        //插入高度为0的bar
        height.push_back(0);

        int sum = 0;
        int i = 0;
        while(i < height.size()) {
            if(s.empty() || height[i] > height[s.back()]) {
                s.push_back(i);
                i++;
            } else {
                int t = s.back();
                s.pop_back();
                //这里还需要考虑stack为空的情况
                sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
            }
        }

        return sum;
    }
};
public class Solution {
    /*
    使用动态规划,用left[i]表示第i个柱子可以最多向左延伸至第left[i]个柱子,形成一个矩形,right[i]则表示向右延伸。遍历两次,分别计算出这两个数组。再遍历一次,即可求出所有的柱子可以形成的最大的矩形面积。为了减少边界的判断,可以使用哨兵,在两端添加两个柱子高度都为-1.
    */
    public int largestRectangleArea(int heights[]){
        int ans = 0;
        int n = heights.length;
        int left[] = new int[n+1];
        int right[] = new int[n+1];
        processLR(heights, left, right);
        for(int i=1; i<=n; i++){
            int tmp = (right[i]-left[i]+1) * heights[i-1];
            if( ans < tmp)
                ans = tmp;
        }
        return ans;
    }

    public void processLR(int heights[], int left[], int right[]){
        int n = heights.length;
        //用临时数组,设置两个哨兵
        int tempArr[] = new int[n+2];
        tempArr[0] = -1;
        for(int i=1; i<=n; i++) tempArr[i] = heights[i-1];
        tempArr[tempArr.length-1] = -1;

        for(int i=1; i<=n; i++){
            int k = i;
            while( tempArr[i] <= tempArr[k-1])
                k = left[k-1];
            left[i] = k;
        }

        for(int i=n; i>0; i--){
            int k = i;
            while(tempArr[i] <= tempArr[k+1])
                 k = right[k+1];
            right[i] = k;
        }
    }
}

Meta

发布: 十二月 4, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 509

下一篇: leetcode刷题 Text Justification

上一篇: leetcode刷题 Binary Tree Maximum Path Sum

Bookmark and Share

Tags

code leetcode

comments powered by Disqus

返回顶部