Leetcode 162) Find Peak Element

10 Sep 2021 in Algorithms

내 답안

class Solution {
    public int trap(int[] height) {
        int rain=0;
        int[] l = new int[height.length];
        int[] r = new int[height.length];
        int max=-1;
        for(int i=0;i<height.length;i++){
            if(height[i]>max){
                max=height[i];
            }
            l[i]=max;

        }
        max=-1;
        for(int i =height.length-1;i>=0;i--){
            if(height[i]>max){
                max=height[i];
            }
            r[i]=max;
        }
        for(int i=0;i<height.length;i++){
            int tmp = Math.min(l[i],r[i])-height[i];
            if(tmp>0){
                rain+=tmp;
            }

        }


        return rain;
    }
}

정답

class Solution {
    public int trap(int[] height) {
        if(height.length == 0)
            return 0;
        int maxleft = height[0];
        int maxright = height[height.length-1];
        int l = 0, r = height.length-1;
        int res = 0;
        while(l <= r) {
            if(maxleft < maxright) {
                maxleft = Math.max(maxleft, height[l]);
                res += (maxleft - height[l]);
                l++;
            } else {
                maxright = Math.max(maxright, height[r]);
                res += (maxright - height[r]);
                r--;
            }
        }
        return res;
    }
}

오답

• 와 그래두 timelimit 뜨기 전에 맞음!!!
• 논리가 맞았당!!!!
• 

class Solution {
    public int trap(int[] height) {
        int sofar=0;
        int rain=0;
        for (int i = height.length-1;i>=0;i--){
            if(height[i]>=sofar){
                while(height[i]>=sofar){
                    for(int j=0;j<i;j++){
                        if(height[j]>=sofar){
                            while(j<i){
                                if(height[j]-sofar<0){
                                    rain++;
                                }
                                j++;
                            }
                        }
                    }
                    sofar++;                    
                }

            }
        }
        return rain;
    }
}