Lettcode----84. 柱状图中最大的矩形

方法一：暴力

遍历所有柱子，对于一根柱子将它向左右扩展算出面积，若比最大面积大则更新最大面积。时间复杂度$O(n^2)$

int largestRectangleArea(vector<int>& heights) {
    int len = heights.size();
    if(len == 0)
        return 0;
    int ans = 0;
    for(int i = 0;i < len;i++)
    {
        int now_num = heights[i];
        int num = 0;
        for(int j = 0;j < len;j++)
        {
            if(heights[j] >= now_num)		//可以扩展
                num += now_num;
            else{							//无法扩展停下
                ans = max(ans,num);
                num = 0;
            }
        }
        ans = max(ans,num);
    }
    return ans;
}

方法二：分治

上述方法复杂度为$O(n^2)$，会超时。我们每次可以找到区间内的最小柱子，其所能勾勒出的面积为柱子的高度乘以区间长度。每找到一个柱子可以将其左右划分为两个子子问题，采用分治的思想解决问题。平均复杂度为$O(nlogn)$，但是当数组为升序或者降序时复杂度还是为$O(n^2)$。

题目所给函数的返回值为int，但是heights[mid]*(r-l+1)这个式子居然会爆int，需要将其改为long long int，而且c++自带的max函数的参数为int类型，我们还需要自己写一个比较。如果嫌上述操作麻烦我们可以用java代码来实现。

c++版

int largestRectangleArea(vector<int>& heights) {
    int len = heights.size();
    if(len == 0)
        return 0;
    return Binary_search(0,len-1,heights);
}
int Binary_search(int l,int r,vector<int>& heights)
{
    if(l > r)
        return 0;
    int mid = l;
    for(int i = l;i <= r;i++)
    {
        if(heights[mid] > heights[i])
        {
            mid = i;
        }
    }
    long long int a = heights[mid]*(r-l+1);
    long long int b = max(Binary_search(mid+1,r,heights),Binary_search(l,mid-1,heights));
    if(a < b)
    {
        long long int t = a;
        a = b;
        b = t;
    }
    return a;
}

java版

public int largestRectangleArea(int[] heights) {
    int len = heights.length;
    if(len == 0)
        return 0;
    return Binary_search(0,len-1,heights);
}
public int Binary_search(int l,int r,int[] heights)
{
    if(l > r)
        return 0;
    int mid = l;
    for(int i = l;i <= r;i++)
    {
        if(heights[mid] > heights[i])
        {
            mid = i;
        }
    }
    return Math.max(heights[mid]*(r-l+1),Math.max(Binary_search(mid+1,r,heights),Binary_search(l,mid-1,heights)));
}

方法三：分治+线段树

方法二最坏的时间复杂度为$O(n^2)$，因为分治最坏情况是$O(n)$，而且我们每次查询一个区间的最小值的时间复杂度为$O(n)$，当我们看到区间查询就能想到线段树了，我们通过线段树来维护区间的最小值，就可以将查询的复杂度降为$O(logn)$了，所以我们算法的最坏时间复杂度为$O(nlongn)$。

    int tree[100000*3];
    int cnt,min_num,indx;
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        if(len == 0)
            return 0;
        cnt = 0;
        create_tree(0,len - 1,1,heights);       //建树
        return Binary_search(0,len-1,heights);
    }
    int Binary_search(int l,int r,vector<int>& heights)     //分治
    {
        if(l > r)
            return 0;
        min_num = heights[l];
        indx = l;
        find(l,r,0,heights.size()-1,1,heights);
        int mid = indx;     //由于indx为全局变量，防止后面的操作改变其值，用mid接收它
        long long int b = max(Binary_search(mid+1,r,heights),Binary_search(l,mid-1,heights));
        long long int a = (long long int)heights[mid]*(r-l+1);
        if(a < b)
        {
            long long int t = a;
            a = b;
            b = t;
        }
        return a;
    }
    void updata(int k,vector<int>& heights)     //维护线段树
    {
        //父节点的值为左儿子和右儿子的最小值
        if(heights[tree[k << 1]] < heights[tree[(k << 1) | 1]])
        {
            tree[k] = tree[k << 1];
        }
        else tree[k] = tree[(k << 1) | 1];
    }
    void create_tree(int l,int r,int k,vector<int>& heights)        //建树
    {
        if(r == l)
        {
            tree[k] = cnt++;
            return;
        }
        int mid = (l + r) >> 1;
        create_tree(l,mid,k << 1,heights);
        create_tree(mid+1,r,(k << 1) | 1,heights);
        updata(k,heights);
    }
    void find(int find_l,int find_r,int l,int r,int k,vector<int>& heights)//区间查询
    {
        if(find_l <= l && r <= find_r)
        {
            if(min_num > heights[tree[k]])
            {
                min_num = heights[tree[k]];
                indx = tree[k];
            }
            return;
        }
        int mid = (l + r) >> 1;
        if(mid >= find_l) find(find_l,find_r,l,mid,k << 1,heights);
        if(find_r >= mid+1) find(find_l,find_r,mid+1,r,(k << 1) | 1,heights);
    }

方法四：单调栈
对于一个柱子我们要能确定它所能勾勒的最大面积的条件是：知道左边和右边比它小的柱子的位置。因为只有碰到比它小的柱子时它才无法扩展，当它无法向左右扩展时说明此时是它所能勾勒的最大面积。方法一其实就是这个思想，但是它每次都要遍历来寻找边界位置，需要两层循环，我们是否可以考虑将其边界缓存下来，只用一次遍历来完成操作。

我们维护一个单调栈，其单调性质为从栈底到栈顶单调递增(其实这样我们就将左边界缓存下来了)。

对于当前的一个柱子来说：
1.它比栈顶小则说明它是栈顶的右边界，此时栈顶的最大面积已经确定可将其弹出，其最大面积的算法为：$已经弹出柱子的高度\times(当前柱子的位置-栈顶柱子的位置-1)$。循环上述过程直到其满足单调栈的性质将其入栈。
2.若它比栈顶大则将其入栈。

操作到最后，栈中还会剩余一些柱子，这时所有柱子的右边界都可以看成最大下标+1，当再剩一个柱子时其左边界为-1(表示没有柱子可扩展)。

对于栈中的元素我们需要知道其高度和位置，我们只需要将其位置存在栈中，可通过数组索引来直到高度。

上述过程自己动手画图过一遍就可以明白。
由于每个柱子只入栈和出栈各一次，所以时间复杂度为$O(n)$

int largestRectangleArea(vector<int>& heights) {
    int len = heights.size();
    if(len == 0)
        return 0;
    int ans = 0,indx;
    stack<int>s;
    s.push(-1);//添加哨兵
    for(int i = 0;i < len;i++)
    {
    	//找到右边界
        while(!s.empty() && s.top() >= 0 && heights[s.top()] > heights[i])
        {
            indx = s.top();
            s.pop();
            
            //将高度相同的柱子全部弹出
            while(!s.empty() && s.top() >= 0 && heights[s.top()] == heights[indx])
            {
                indx = s.top();
                s.pop();
            }
            
            if(!s.empty())
                ans = max(ans,heights[indx]*(i - s.top() - 1));
        }
        s.push(i);
    }
    while(!s.empty())
    {
        indx = s.top();
        s.pop();
        if(!s.empty())
            ans = max(ans,heights[indx]*(len - s.top() - 1));
    }
    return ans;
}

转载：https://blog.csdn.net/qq_39781096/article/details/105323147