simple solution c++ O(n)


  • 0

    class Solution {
    public:
    // vector<vector<int>>table;
    // void dp(vector<vector<int>>&table,int i,int j){
    // if()
    // }
    int trap(vector<int>& height) {
    if(height.size()<3)return 0;
    int head=0,cur=0,tmp=0,res=0,tail=height.size()-1;
    here:
    if(tail==head)return res;
    while(height[cur]<height[head]&&cur!=height.size()){
    tmp+=height[head]-height[cur];
    cur++;
    }
    if(cur==height.size()&&tmp==0)return res;
    if(cur==height.size()&&tmp!=0)goto there;
    head=cur;
    cur++;
    res+=tmp;
    tmp=0;
    goto here;

        there:
        cout<<head<<","<<tail<<","<<res<<endl;
        tmp=0;
        if(tail==head)return res;
        cur=tail-1;
        while(height[cur]<height[tail]&&cur>=head){
            tmp+=height[tail]-height[cur];
            cur--;
        }
        res+=tmp;
        if(cur==head)return res;
        tail=cur;
        cur--;
        tmp=0;
        goto there;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.