63      技術社區[雲棲]

龐果網之尋找直方圖中麵積最大的矩形

【解析】

使用一個棧來保存輸入柱狀條，每個柱狀條包含兩個信息：（1）柱狀條的高度(height)；（2）柱狀條的寬度(width) 。初始寬度均為單位寬度1。

在隨後的入棧和出棧中隨時更改柱狀條的寬度。

（1）當入棧柱狀條的高度大於棧頂柱狀條的高度或者棧為空時，柱狀條入棧；如圖1

（2）當入棧柱狀條的高度小於棧頂柱狀條的高度時，柱狀條出棧，同時計算出棧的柱狀條的麵積，更新最大矩形麵積。同時更新當前柱狀條的寬度。如圖2

（3）當入棧柱狀條的高度等於棧頂柱狀條的高度時，柱狀條出棧，更新當前柱狀條寬度。如圖3

（4）如果最後棧不空，隻剩高度遞增的柱狀條。一個一個出棧，更新最大矩形麵積。每一個柱狀條出棧都要更新前一個柱狀條的寬度。如圖4

寫的不好，勿噴。

【代碼】

/*********************************
*   日期：2013-11-24
*   作者：SJF0115
*   題號: 尋找直方圖中麵積最大的矩形
*   來源：https://hero.pongo.cn/Question/Details?ID=58&ExamID=56
*   結果：AC
*   來源：龐果網
*   總結：
**********************************/
#include<iostream>
#include<stack>
#include<vector>
#include<stdio.h>
#include<malloc.h>
using namespace std;

typedef struct Rec{
    int height;
    int width;
}Rec;

int LargestRectangleArea(vector<int> &height){
    int Max = 0,i;
    int n = height.size();
    //容錯處理
    if(n <= 0){
        return 0;
    }
    Rec *rec = (Rec*)malloc(sizeof(Rec)*n);
    stack<Rec> stack;
    //初始化
    for(i = 0;i < n;i++){
        rec[i].height = height[i];
        rec[i].width = 1;
    }
    for(i = 0;i < n;i++){
        int h = rec[i].height;
        //如果棧空或者當前高度大於棧頂的矩形高度的時候就壓入棧
        if(stack.empty() || h > stack.top().height){
            stack.push(rec[i]);
        }
        else{
            int preWidth = 0;
            //小於棧頂的矩形高度就彈出棧,更新最大的矩形麵積
            while(!stack.empty() && h < stack.top().height){
                rec[i].width += stack.top().width;
                //當前麵積
                int currentMax = stack.top().height * (stack.top().width + preWidth);
                //更新最大值
                if(Max < currentMax){
                    Max = currentMax;
                }
                preWidth += stack.top().width;
                //出棧
                stack.pop();
            }
            //等於棧頂的矩形高度
            while(!stack.empty() && h == stack.top().height){
                rec[i].width += stack.top().width;
                stack.pop();
            }
            //棧空
            if(stack.empty() || h > stack.top().height){
                stack.push(rec[i]);
            }
        }
    }
    //最後棧中隻剩遞增的序列
    int width = 0;
    while(!stack.empty()){
        int currentMax = stack.top().height * (stack.top().width + width);
        if(currentMax > Max){
            Max = currentMax;
        }
        width += stack.top().width;
        stack.pop();
    }
    return Max;
}

int main(){
    int i,n,Max,num;
    while(scanf("%d",&n) != EOF){
        vector<int> height;
        for(i = 0;i < n;i++){
            scanf("%d",&num);
            height.push_back(num);
        }
        Max = LargestRectangleArea(height);
        printf("%d\n",Max);
    }
    return 0;
}

【方法二】

【解析】

設柱狀圖為非負整數數組A, 則最大矩形的高度必定是數組的某一項height[i]。

設f(i) 為以數組第i項的高度為矩形高度時矩形的最大寬度，則最大矩形為max{f(i)*height[i]}  (0 <= i < n)

f(i)本身無法動態規劃，但若將f(i)拆成左右兩部分，則很容易動態規劃求解

令left(i)為以數組第i項為矩形高度時矩形左側最大寬度，

  right(i)為以數組第i項為矩形高度時矩形右側最大寬度，

則f(i) = left(i) + right(i) - 1

【代碼】

/*********************************
*   日期：2013-11-25
*   作者：SJF0115
*   題號: 尋找直方圖中麵積最大的矩形
*   來源：https://hero.pongo.cn/Question/Details?ID=58&ExamID=56
*   結果：AC
*   來源：龐果網
*   總結：
**********************************/
#include <stdio.h>

int left[100001],right[100001];

int largestRectangleArea(const int *height,int n) {
    int Max = 0,i,j;
    //容錯處理
    if(height == NULL || n <= 0){
        return 0;
    }
    left[0] = 1;
    right[n-1] = 1;
    //以數組第i項為矩形高度時矩形左側最大寬度
    for(i = 1;i < n;i++){
        //初始為單位寬度1
        left[i] = 1;
        for(j = i-1;j >= 0;){
            if(height[i] <= height[j]){
                left[i] += left[j];
                //跳到下一個比較對象
                j -= left[j];
            }
            else{
                break;
            }
        }
        //printf("第%d項左最大寬度：%d\n",i+1,left[i]);
    }
    //以數組第i項為矩形高度時矩形右側最大寬度
    for(i = n-2;i >= 0;i--){
        //初始為單位寬度1
        right[i] = 1;
        for(j = i+1;j < n;){
            if(height[i] <= height[j]){
                right[i] += right[j];
                //跳到下一個比較對象
                j += right[j];
            }
            else{
                break;
            }
        }
        //printf("第%d項右最大寬度：%d\n",i+1,right[i]);
    }
    for(i = 0;i < n;i++){
        int currentMax = (left[i] + right[i] - 1) * height[i];
        if(Max < currentMax){
            Max = currentMax;
        }
    }
    return Max;
}



//start 提示：自動閱卷起始唯一標識，請勿刪除或增加。
int main()
{
    int height[] = {1,2,3,4,3,4,3,2,1};
    int max =  largestRectangleArea(height,9);
    printf("%d\n",max);
    return 0;
}
//end //提示：自動閱卷結束唯一標識，請勿刪除或增加。

【測試數據】

｛1，2，3，4，3，4，3，2，1｝ 結果： 15

｛3，4，5，6}   結果：12

｛2，1，2，1，2，1｝ 結果：6

｛2，1，5，6，2，3｝結果：10

｛2, 1, 4, 5, 1, 3, 3, 1, 2} 結果：9

最後更新：2017-04-03 14:54:25

  上一篇： 給出任意一個正整數，算出大於它的最小不重複數——最高效[2014百度筆試題]

  下一篇： 龐果網之楊輝三角的變形