leetcode 姆咪姆咪

[oin1104 (是oin的說)]

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


題目要你算出這串陣列

下雨之後能積多少水



我是

直接從左邊stack到右邊

如果沒stack好

那就是左邊最高的地方比右邊都高

那就再從右邊stack到左邊

就成功惹



這是我第一次自己想出hard的解法

第一次自己寫出hard

好開心捏


int trap(int* height, int heightSize)
{

    int rain = 0;

    int stack[20001] = {};
    int stack2[20001] = {};

    //stack[stackp][0] = 值

    stack[0] = height[0];

    int stackp = 0;

    int stand = height[0] ;

    for(int i = 1 ; i < heightSize ; i ++)
    {
        if(height[i] < stand)
        {
            stackp ++ ;
            stack[stackp]= height[i];
        }
        if(height[i] >= stand)
        {
            int b = stackp;

            for(b ; b > 0 ; b--)
            {
                rain += (stand - stack[b]);
                stack[b] = 0;
            }

            stack[0] = height[i] ;
            stand = height[i] ;
            stackp = 0;
        }

    }
    stand = stack[stackp];

    int stackp2 = 0;
    stack2[0] = stackp;
    for(int q = stackp ; q >= 0 ; q --)
    {
        if(stack[q] < stand)
        {
            stackp2 ++ ;
            stack2[stackp2]= stack[q];
        }
        if(stack[q] >= stand)
        {
            int b = stackp2;

            for(b ; b > 0 ; b--)
            {
                rain += (stand - stack2[b]);
                stack2[b] = 0;
            }

            stack2[0] = stack[q] ;
            stand = stack[q] ;
            stackp2 = 0;
        }
    }
    return rain;

}



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.57.64 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700364249.A.E2A.html
→ scmono: 大師