程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 尋找直方圖中面積最大的矩形(C語言版)

尋找直方圖中面積最大的矩形(C語言版)

編輯:關於C語言

注:我是用循環實現的,肯定不是最優的算法,歡迎留言討論。(題目來自龐果網)

題目詳情:

給定直方圖,每一小塊的height由N個非負整數所確定,每一小塊的width都為1,請找出直方圖中面積最大的矩形。


如下圖所示,直方圖中每一塊的寬度都是1,每一塊給定的高度分別是[2,1,5,6,2,3]:


\


<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPC9ibG9ja3F1b3RlPgo8L2Jsb2NrcXVvdGU+CjxwPgogICDEx8O0yc/K9taxt73NvNbQo6zD5rv91+6087XEvtjQzrHjysfPws28y/nKvrXE0vXTsLK/t9a1xMPmu/2jrMPmu/09IDEwtaXOu6GjPC9wPgo8YmxvY2txdW90ZT4KPGJsb2NrcXVvdGU+CjxwPgo8YnI+CjwvcD4KPGJsb2NrcXVvdGU+CjxwPgo8aW1nIHNyYz0="http://www.Bkjia.com/uploadfile/Collfiles/20131220/20131220132908209.png" alt="\">


請完成函數largestRectangleArea,實現尋找直方圖中面積最大的矩形的功能,如當給定直方圖各小塊的高度= [2,1,5,6,2,3] ,返回10。

解題代碼:

int minElement(const int *h, int b, int e)
{
    int min = h[b++];
    for (; b < e; ++b)
    {
        if (h[b] < min)
            min = h[b];
    }
    return min;
}

int largestRectangleArea(const int *height,int n) {
    int max = 0;
    int min = 0;
    int i, j;
    for (i = 0; i < n; ++i)
    {
        for (j = i; j < n; ++j)
        {
            min = minElement(height, i, j + 1);
            if ((j+1-i)*min > max)
            {
                max = (j+1-i)*min;
            }
        }
    }
    return max;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved