leetcode 姆咪姆咪

[oin1104 (是oin的說)]

https://i.imgur.com/pt05Jcx.png

這大概是我這輩子目前解過 最難的題目了

雖然基本上都是我同學在教我

謝謝同學

謝謝 謝謝喔

題目 找出一串陣列的最大矩形

然後 我其實根本沒想出解法

是他想到的

他的解法原理就是

先找到最小的數字他的矩形

再往左右找次小的矩形

比較他們的面積大小

然後透過遞迴不斷的找矩形

直到找到最大的

我只是

實現他的原理而已

我沒想到解法

不過還是花了我一整天來寫跟理解

我流淚了


int largestRectangleArea(int* heights, int heightsSize)
{
    if(heightsSize == 0)
    {
        return 0;
    }


    if(heightsSize == 1)
    {
        return heights[0];
    }

    int min = heights[0];
    int minp = 0;

    int rmax = 0 ;
    int lmax = 0 ;
    int nmax = 0 ;

    int ans = 0;


    for(int i = 0 ; i < heightsSize ; i ++)
    {
        if(heights[i] < min)
        {
            min = heights[i];
            minp = i;
        }
    }


    int leftsize = minp ;
    int rightsize = heightsSize - minp - 1 ;

    int rp = minp ;

    while(rp+1 < heightsSize && (heights[rp] == heights[rp+1] ))
    {
        rp ++;
        rightsize --;
    }

    lmax = largestRectangleArea( heights, leftsize);

    rmax = largestRectangleArea( heights+rp+1, rightsize);



    nmax = heights[minp]*heightsSize;

    if((nmax >= rmax) && (nmax >= lmax))
    {
        return nmax;
    }
    else if((lmax >= nmax) && (lmax >= rmax) )
    {
        return lmax;
    }
    else if((rmax >= nmax) && (rmax >= lmax))
    {
        return rmax;
    }

    return 0;
}



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700241835.A.D4A.html
→ NTUEE2CS: 還好 我覺得找最大的環比較難搞
→ oin1104: 題目給我一下 我搞不好可以痛苦一個禮拜
→ NTUEE2CS: 你搜尋find largest ring應該就有了
推 h0103661: 你好厲害
→ oin1104: 不是我厲害 是我室友厲害
→ oin1104: 好 我看看
→ oin1104: 我沒看到最大的環那提欸
推 dustsstar79: stack經典題
推 NTHUlagka: 這是哪題啊