C++ solution, thinking inversely,6ms, O(1) space and O(n) time


  • 0
    S

    Instead of directly consider the water that can be trapped, I consider the water leaked, which is the meaning of variable 'minussum' in the code.

            int maxheight = 0, sum = 0;
            for(auto c: height){
                maxheight = max(maxheight, c);
                sum += c;
            }
            int current = 0, minussum = 0;
            for(int i = 0; i<height.size(); i++){
                current = max(current, height[i]);
                minussum += maxheight - current;
                if(current == maxheight){
                    break;
                }
            }
            current = 0;
            for(int i = height.size()-1; i >= 0;i--){
                current = max(current, height[i]);
                minussum += maxheight - current;
                if(current == maxheight){
                    break;
                }
            }
            return maxheight*height.size() - minussum - sum;
        }

Log in to reply
 

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