Solution in C++


  • 1
    P
    class Solution 
    {
    public:
    	int trap(vector<int>& height) 
    	{
    		if (0 == height.size()) return 0;
    		int maxIndex = 0, sum = 0;
    		for (int i = 0; i < height.size(); ++i)
    			if (height[maxIndex] < height[i])
    				maxIndex = i;
    		trap(height, 0, maxIndex, sum);
    		trap(height, maxIndex, height.size() - 1, sum);
    		return sum;
    	}
    private:
    	void trap(vector<int>& height, int lo, int hi, int& sum) 
    	{
    		if (lo == hi) return;
    		if (height[lo] >= height[hi]) 
    		{
    			int maxIndex = lo + 1;
    			for (int i = lo + 1; i <= hi; ++i)
    				if (height[maxIndex] < height[i])
    					maxIndex = i;
    			for (int i = lo + 1; i <= maxIndex; ++i)
    				sum += height[maxIndex] - height[i];
    			trap(height, maxIndex, hi, sum);
    		}
    		else 
    		{
    			int maxIndex = hi - 1;
    			for (int i = hi - 1; i >= lo; --i)
    				if (height[maxIndex] < height[i])
    					maxIndex = i;
    			for (int i = hi - 1; i >= maxIndex; --i)
    				sum += height[maxIndex] - height[i];
    			trap(height, lo, maxIndex, sum);
    		}
    	}
    };
    
    class SolutionB
    {
    public:
    	int trap(vector<int>& height) 
    	{
    		if (0 == height.size()) return 0;
    		int sum = 0, maxIndex = 0, lo = 0, hi = 0, temp = 0;
    		for (int i = 0; i < height.size(); ++i)
    			if (height[maxIndex] < height[i])
    				maxIndex = i;
    		lo = hi = maxIndex;
    		while (0 != lo) 
    		{
    			temp = lo - 1;
    			for (int i = lo - 1; i >= 0; --i)
    				if (height[temp] < height[i])
    					temp = i;
    			for (int i = lo - 1; i >= temp; --i)
    				sum += height[temp] - height[i];
    			lo = temp;
    		}
    		while (hi != height.size() - 1)
    		{
    			temp = hi + 1;
    			for (int i = hi + 1; i < height.size(); ++i)
    				if (height[temp] < height[i])
    					temp = i;
    			for (int i = hi + 1; i <= temp; ++i)
    				sum += height[temp] - height[i];
    			hi = temp;
    		}
    		return sum;
    	}
    };

Log in to reply
 

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