[84] Largest Rectangle in Histogram

找柱狀圖的最大面積
其實我的腦中一片空白 囧
我連暴力法都不會寫了Orz
大意是整個array跑一遍, 每次找出它的第一個比它小的左邊, 跟第一個比它小的右邊,
將右減左減一當做寬,它自己當做高, 算出它可以擁有的最大面積,
每個item都算出自己的最大面積之後, 再回傳全部裡面的最大的.

看起來是可以用的, 不過不夠快 ：
Largest Rectangle in Histogram
int largestRectangleArea(int* heights, int heightsSize) {
    if (heights==NULL || heightsSize<1)
        return 0;
    else if (heightsSize == 1)
        return heights[0];
    int right[heightsSize];
    int left[heightsSize];
    int i,j, k, max =INT_MIN;

    for(i=0;i<heightsSize;i++)
    {
        left[i]=-1;
        for(j=i;j>=0;j--)
        {
            if(heights[j]<heights[i])
            {
                left[i]=j;
                break;
            }
        }

        right[i]=heightsSize;
        for(k=i;k<heightsSize;k++)
            if(heights[k]<heights[i])
            {
                right[i]=k;
                break;
            }

        int area = (right[i]-left[i]-1)*heights[i];
        if (area > max)
            max = area;
    }

    return max;
}

然後就是說用同樣的精神,
只是在找出左邊的第一個最小和右邊的第一個最小的這個部分,
用stack來完成.
每一個item會進去stack一次,
如果stack是空的, push進去;
如果目前的item 比stack的top 大, 也push進去;
如果目前的item 比stack的top 小, 那目前item的index可以當做右邊第一個最小,
stack的top 的value是我們的高, stack top的前一個的index 是左邊第一個做小,
如此可以算出stack top 可以有的最大面積.
算完把它pop掉, stack的top會更新, 用新的top來看目前的item 要被push進去,
還是要來算新的top的面積, 直到做完.

typedef struct _stack{
    int value;
    int index;
} stack;

int largestRectangleArea(int* heights, int heightsSize) {
    if (heights==NULL || heightsSize<1)
        return 0;
    stack myStack[heightsSize];
    int i, head=-1, max = INT_MIN;

    for(i=0;i<heightsSize;i++)
    {
        if (head < 0 || heights[i] >= myStack[head].value)
        {
            myStack[++head].value = heights[i];
            myStack[head].index = i;
        }
        else
        {
            while(head >= 0 && heights[i]<myStack[head].value)
            {
                int index = (head-1)>=0 ? (myStack[head-1].index) : -1;
                int area = (i- index -1) * myStack[head--].value;
                if (area > max)
                    max= area;
            }
            myStack[++head].value = heights[i];
            myStack[head].index = i;
         
        }
    }
    while(head >= 0)
    {
        int index = (head-1)>=0 ? (myStack[head-1].index) : -1;
        int area = (i- index -1) * myStack[head--].value;
        if (area > max)
            max= area;
    }
    return max;
}
這一題可以拿來做[85] Maximal Rectangle (比樓下樓下樓下)
每行row 先往上算出它的 height (在這行row當做基底時, 每一個column往上看有幾個連續的 1 )
如此每行row 都可以套用Largest Rectangle in Histogram 找出它當下的最大面積
最後再回傳每行row最大面積的最大面積(跳針XD).