leetcode84. Largest Rectangle in Histogram 分治+线段树

题目大意：输入一个整数数组，每个整数表示一个宽度为1的矩形，相邻整数对应的矩形相邻，求所有矩形的区域里面，围成的面积最大矩形的面积。

链接：https://leetcode.com/problems/largest-rectangle-in-histogram/

我们以输入[2,1,5,6,2,3]为例。

最大的矩形是高度为5的矩形和高度为6的矩形构成的，面积为10。

我们可以发现，给定起始和终止的两个矩形，这两个矩形围成的面积取决于这个区间内最矮的那个矩形。例如我求以第一个矩形起始，以最后一个矩形结尾的面积。这个面积取决于这个区间内最矮的矩形高度1，这个面积为1×(5-0+1)=6。

所以一开始我的思路就是分治的思路：最大的矩形面积，

要么是0～5最矮的矩形的高×（0～5区间长度）

要么是最矮矩形右边区域的最大面积。（递归求解）

要么是最矮矩形左边区域的最大面积。（递归求解）

最大矩形面积就是求三者的最大值。

那么这里还涉及到一个问题，就是如何找最矮的矩形，我一开始的想法就是线性查找，但这是一种效率很低的查找方式。这是我一开始的求解代码，800多毫秒的运行时间：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size()==0) return 0;
        return largest(heights,0,heights.size()-1);
    }
    int largest(vector<int>& heights,int l,int r){
        //cout<<"l="<<l<<" r="<<r<<endl;
        if(l==r) return heights[l];
        else if(l>r) return 0;
        
        int min=heights[l],min_index=l;
        for(unsigned int i=l;i<=r;++i){
            if(heights[i]<min){
                min=heights[i];
                min_index=i;
            }
        }
        
        int num1=min*(r-l+1);
        int num2=largest(heights,l,min_index-1);
        int num3=largest(heights,min_index+1,r);
        int ret=max(num1,num2);
        ret=max(ret,num3);
        return ret;
    }
};

其实分治法的思路没有问题，就是查找最矮矩形使用的方法可以再优化。这道题我们的需求就是查找某个区间上的最值问题。区间查找（根据网上答案提示），可以用线段树。于是我修改了一下，得到了优化以后的方法，运行时间20ms：

struct SegNode{
    int l,r;//interval[l,r]
    int index;//最小高度的下标
};
class Solution {
public:
    vector<SegNode> seg_tree;
    
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size()==0) return 0;
        else if(heights.size()==1) return heights[0];
        
        seg_tree.resize(4*heights.size());
        buildSegmentTree(heights,1,0,(int)heights.size()-1);
        
        return largest(heights,0,heights.size()-1);
    }
    
    void buildSegmentTree(vector<int>& heights,int index,int l,int r);
    
    int search(vector<int>& heights,int index,int l,int r);
    
    int largest(vector<int>& heights,int l,int r){
        if(l>r) return 0;
        else if(l==r) {
            //cout<<"largest"<<"  l="<<l<<"  r="<<r<<"  ret="<<heights[l]<<endl;
            return heights[l];
        }
        
        int min_index=search(heights,1,l,r);
        
        //cout<<"min_index="<<min_index<<endl;
        
        int num1=heights[min_index]*(r-l+1);
        
        int num2=largest(heights,l,min_index-1);
        
        //cout<<"num2="<<num2<<endl;
        
        int num3=largest(heights,min_index+1,r);
        
        //cout<<"num3="<<num3<<endl;
        
        int ret=max(num1,num2);
        ret=max(ret,num3);
        //cout<<"largest"<<"  l="<<l<<"  r="<<r<<"  ret="<<ret<<endl;
        return ret;
    }
};


void Solution::buildSegmentTree(vector<int>& heights,int index,int l,int r){
    if(l==r){
        seg_tree[index].l=seg_tree[index].r=l;
        seg_tree[index].index=l;
        //cout<<"l="<<l<<" r="<<r<<"  index="<<seg_tree[index].index<<endl;
        return;
    }
    int mid=(l+r)/2;
    
    buildSegmentTree(heights,index<<1,l,mid);
    buildSegmentTree(heights,(index<<1)|1,mid+1,r);
    seg_tree[index].l=l;
    seg_tree[index].r=r;
    
    
    int l_min=seg_tree[index<<1].index;
    int r_min=seg_tree[(index<<1)|1].index;
    if(heights[l_min]<heights[r_min]) seg_tree[index].index=l_min;
    else seg_tree[index].index=r_min;
    
    
    //cout<<"l="<<l<<" r="<<r<<"  index="<<seg_tree[index].index<<endl;
    return;
}

//interval[l,r],minimun index
int Solution::search(vector<int>& heights,int index,int l,int r){
    int mid=(l+r)/2;
    if(l<=seg_tree[index].l && r>=seg_tree[index].r) return seg_tree[index].index;
    
    int num1=INT_MAX;
    if(l<=seg_tree[index<<1].r){
        num1=search(heights,index<<1,l,r);
    }
    
    int num2=INT_MAX;
    if(r>=seg_tree[(index<<1)|1].l) num2=search(heights,(index<<1)|1,l,r);
    
    if(num1!=INT_MAX && num2!=INT_MAX){
        if(heights[num1]<heights[num2]) return num1;
        else return num2;
    }else if(num1==INT_MAX) return num2;
    else return num1;
    
}