LeetCode 42. Trapping Rain Water

旧城等待， 2023-06-04 04:57 2阅读 0赞

[题目][Link 1]

1A  
c++

O(n^2)

class Solution {
    public:
        
        int trap(vector<int>& height) {
            
            int ans=0;
            for(int i=1;i<height.size();i++)
            {
                if(height[i]>height[i-1])
                {
                    int pos=0;
                    for(int j=i-2;j>=0;j--)
                    {
                        if(height[j+1]<height[j])
                        {
                            int h=min(height[j],height[i]);
                            for(int k=j+1;k<=i-1;k++)
                            {
                                ans += h-height[k];
                                height[k] += h-height[k];
                               
                            }
                            
                            if(height[i]<height[j])
                                break;
                        }
                    }
                }
            }
            
            return ans;
            
        }
    };

O(n)

class Solution {
    public:
        int left[100005];
        int right[100005];
        int trap(vector<int>& height) {
            
            
            int ans=0;
            if(height.size()==0)
                return ans;
            left[0] = height[0];
            for(int i=1;i<height.size();i++)
            {
                left[i] = max(left[i-1],height[i]);
            }
            
            right[height.size()-1] = height[height.size()-1];
            
            for(int j=height.size()-2;j>=0;j--)
            {
                right[j]=max(right[j+1],height[j]);
            }
            
            for(int i=0;i<height.size();i++)
            {
                ans += min(left[i],right[i]) - height[i];
            }
            
            return ans;
            
        }
    };

转载于:https://www.cnblogs.com/dacc123/p/11344908.html

[Link 1]: https://leetcode.com/problems/trapping-rain-water/