A fast and easy-understand cpp solution


  • 12
    T
        int maxArea(vector<int> &height) {
            int l(0), r=height.size()-1, result(0);
            while(l < r){
                if(height[l] < height[r]){
                     result =  max(result, height[l] * (r - l));
                     int pivot = height[l++];
                     while(l < r && height[l] <= pivot) ++l;
                }else{
                     result = max(result, height[r] * (r - l));
                     int pivot = height[r--];
                     while(l < r && height[r] <= pivot) --r;
                }
            }
            return result;
        }

  • 0
    T

    python version:

      def maxArea(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            l, r, result = 0, len(height)-1, 0
            while l < r:
                if height[l] < height[r]:
                    result = max(result, (r-l) * height[l]);
                    pivot = height[l]
                    l += 1
                    while l < r and height[l] <= pivot: l+=1
                else:
                    result = max(result, (r-l) * height[r]);
                    pivot = height[r]
                    r -= 1
                    while l < r and height[r] <= pivot: r-=1
            return result

  • 0
    D

    Is this solution a sort of greedy algorithm ?


  • 3
    T

    As I see this algorithm has 3 parts.

    1. Checking if there are more possiblities

    Keeping the invariant of l < r means that left is on the left side of right. If l >= r, it means that:

    • the left is either the same as right (0-width -> 0-area)
    • or they're in the wrong order (negative area).

    This is used in part 3 too.

    2. Finding the max

    if (height[l] < height[r]) {
         result = max(result, height[l] * (r - l));
    } else {
         result = max(result, height[r] * (r - l));
    }
    

    which is the same as

    result = max(result, min(height[l], height[r]) * (r - l));
    

    Consider a container with two sides (l/r):

      |    overflow--._
      |      ----------\
      |  |            | \
      |  |  |         |
    --l---------------r-------
    

    the area of the container is given by the smaller height (r) and their distance (r - l). Cannot choose the other side (l) because the water would just overflow. This is symmetric if we draw the column heights the opposite.

    3. Skipping the values that can't be better

    if (height[l] < height[r]) {
         int pivot = height[l++];
         while(l < r && height[l] <= pivot) ++l;
    } else {
         int pivot = height[r--];
         while(l < r && height[r] <= pivot) --r;
    }
    

    Removing the optimizations (post-increments) and the bounds checking (l < r, see part 1):

    if (height[l] < height[r]) {
         int pivot = height[l];
         while (height[l] <= pivot) ++l;
    } else {
         int pivot = height[r];
         while (height[r] <= pivot) --r;
    }
    

    it's easier to see that it's looking for the next element that is bigger than the pivot.
    The two branches are just for choosing which side to start looking for a better possibility. The smaller side must be chosen, because the area is contained by min(height[l], height[r]) (see part 2).

    Anything smaller than or equal to the pivot can be skipped because:

    1. the distance between current l and r is getting smaller, so area getting smaller too
    2. if a height is smaller than pivot the area is smaller too

    If we find a bigger than pivot height we can hope for a bigger area (depending on how much taller it is).
    The post-increment optimization is just there to not run an unnecessary loop of the while for the pivot itself.


  • 0
    T

    DixuanYang, see my answer.


Log in to reply
 

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