8ms c++ solution


  • 0
    B
    class Solution {
    public:
        int trap(vector<int>& height) {
            int n = height.size();
            int left = -1;
            int i = 0;
            for (; i < n; i++)
            {
                if (height[i] > 0)
                {
                    left = i;
                    break;
                }
            }
    
            if (left == -1 || left == n-1)
            {
                return 0;
            }
    
            int nextMaxPos[n];
            nextMaxPos[n-1] = n-1;
            for (int j = n-2; j >= 0; j--)
            {
                if (height[j] >= height[nextMaxPos[j+1]])
                {
                    nextMaxPos[j] = j;
                }
                else
                {
                    nextMaxPos[j] = nextMaxPos[j+1];
                }
            }
    
            int sum = 0;
            int right = left+1;
            while (right < n)
            {
                if (height[nextMaxPos[right]] <= height[left])
                {
                    right = nextMaxPos[right];
                }
                else
                {
                    for (int j = right; j < n; j++)
                    {
                        if (height[j] >= height[left])
                        {
                            right = j;
                            break;
                        }
                    }
                }
    
                sum += min(height[left], height[right]) * (right-left-1);
                for (int j = left+1; j < right; j++)
                {
                    sum -= height[j];
                }
                left = right;
                while (left < n-1 && height[left] == height[left+1])
                {
                    left++;
                }
                right = left + 1;
            }
    
            return sum;
        }
    };

Log in to reply
 

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