[LeetCode Largest Rectangle in Histogram]

题意：给出一个长度n的数组，每个值为非负数，描述一个宽为1的立柱的高h[i]，求立柱围成区域中最大的矩形区域面积。

分析：
对于每个立柱i，求出满足h[j]到h[i-1]都不小于h[i]的最左值j，记i-j+1为lc[i]，类似地求出rc[i]，那么位置i对应的最大可行面积即为h[i]*(lc[i]+rc[i]+1)。

以求lc[i]为例，需要一个单调栈，单调栈中由底到顶依次记录扫描到i之前的上升序列d[l]及其位置di[l]，扫描到i时，初始化lc[i]=1，对于所有高度d[l]大于等于h[i]的栈顶元素，依次出栈，并将其lc[di[l]]加到lc[i]中，最后将h[i]和i入栈。

时间复杂度方面，计算lc和rc时，每个元素刚好入栈、出战各一次，因此根据平摊分析，时间复杂度是O(n)的。

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {
public:
    int largestRectangleArea(vector<int> &h) {
        n=h.size(); ans=0;
        int i, l;
        for(i=0, l=0; i<n; i++)
        {
            for(lc[i]=1; l&&h[i]<=d[l-1]; l--)
                lc[i]+=lc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=n-1, l=0; i>-1; i--)
        {
            for(rc[i]=1; l&&h[i]<=d[l-1]; l--)
                rc[i]+=rc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=0; i<n; i++)
            ans=max(ans, h[i]*(lc[i]+rc[i]-1));
        return ans;
    }
};

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {

public:

int largestRectangleArea(vector<int> &h) {

n=h.size(); ans=0;

int i, l;

for(i=0, l=0; i<n; i++)

{

for(lc[i]=1; l&&h[i]<=d[l-1]; l--)

lc[i]+=lc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=n-1, l=0; i>-1; i--)

{

for(rc[i]=1; l&&h[i]<=d[l-1]; l--)

rc[i]+=rc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=0; i<n; i++)

ans=max(ans, h[i]*(lc[i]+rc[i]-1));

return ans;

}

};

ps：最早是半年前被问到了这题。现在回头看看，写得真是惨不忍睹。现在做LeetCode又遇到这题，分析题意方面，要比之前稍好一些了吧……