Re: [閒聊] 每日leetcode

[oinishere (是oin捏)]

這題我是用stack做

一樣是找兩邊最高的 讓他們裝水

然後要兩個stack

不然會有沒裝到水的地方

捏

class Solution {
public:
    int trap(vector<int>& height)
    {
        int water = 0;

        int len = height.size();

        vector<int> paper;
        vector<int> paper2;

        for(int i = 0 ; i < len ; i ++)
        {
            paper.push_back(i);

            int tall = 0;
            int talli = 0;
            if(paper.size() > 1 && height[paper[0]] <= height[paper[paper.size()
-1]])
            {
                tall = min(height[paper[0]] , height[paper[paper.size()-1]] );
                talli = i;
                for(int j = paper[0]+1 ; j < paper[paper.size()-1] ; j ++)
                {
                    water += tall - height[j];
                    //cout << tall << " - " << height[j] << " (" << j << endl;
                }
                paper.clear();
                paper.push_back(i);
            }
        }

        for(int i = paper.size()-1 ; i >= 0 ; i --)
        {
            paper2.push_back(paper[i]);

            int tall = 0;
            int talli = 0;
            if(paper2.size() > 1 && height[paper2[0]] <= height[paper2[paper2.si
ze()-1]])
            {
                //cout << "???" ;
                tall = min(height[paper2[0]] , height[paper2[paper2.size()-1]] )
;
                talli = paper2[paper2.size()-1];
                for(int j = paper2[0] ; j > paper2[paper2.size()-1] ; j --)
                {
                    water += tall - height[j];
                    //cout << tall << " - " << height[j] << " (" << j << endl;
                }
                paper2.clear();
                paper2.push_back(talli);
            }
        }

        return water;


    }
};


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.47.173 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712891409.A.F87.html
→ wwndbk: 大師
推 wu10200512: 為啥要取名叫paper
→ oinishere: 因為我喜歡拿紙畫畫寫題目 算我的習慣
→ oinishere: 畫畫寫題目想東西都拿紙
推 JIWP: 這題去年就寫過了
→ oinishere: 我去年是用c寫的 解法跟現在差不多
→ JIWP: 你那時候還跟我說是室友教你的
→ oinishere: 我現在自己寫了 所以現在我會了
推 DJYOSHITAKA: 大師
推 JIWP: 還不是賣py
推 SecondRun: 大師