cropper or striver

cropper or striver

在摆烂与奋进中反复横跳

📗Container with the Most Water Algorithm Practice Check-in Day 2

Difficulty: Medium#

Problem:#

Given an integer array height of length n. There are n vertical lines, where the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines, which together with the x-axis forms a container, such that the container contains the most water.

Return the maximum amount of water that the container can hold.

Note: You may not slant the container.

Analysis#

Can you "see" it at a glance?#

At first glance, this problem seems very simple. Use two loops to calculate the water volume and compare the maximum water volume. There is no need to even keep track of when the water is at its maximum. "See it at a glance"

    public int maxArea(int[] height) {
        //Traversal
        int max = height.length;
        int maxarea = 0;
        for (int n = 0; n < max; n++) {
            for (int m = n; m < max; m++) {
                int temp = (m - n) * Math.min(height[n],height[m]);
                maxarea = Math.max(maxarea,temp);
            }
        }
        return maxarea;

    }

Result

Wow, this is not good. There are too many data points, and the two loops are causing a timeout.

Starting over#

The problem is caused by the two nested loops, so the goal is to reduce the number of loops to one or even fewer.
The hint suggests using two pointers. Starting from the left and right endpoints. If it is possible to move only one pointer in one direction at a time, then it can be done with only one loop. The volume of water is determined by the base of the container (the distance between the two pointers) and the height (the minimum value of the two pointers). The base of the container will only decrease as it moves towards the center. The height is the minimum value of the two pointers, so if the pointer for the higher side is moved, the height of the container will not change. The volume of water may even decrease. Only by moving the pointer for the lower side can the volume of water be increased.
So, the plan is to loop once, move the smaller side each time, compare the water volume each time with the recorded maximum water volume, and find the true maximum water volume.

    public int maxArea(int[] height) {
        //Two pointers
        int max = height.length;
        int i = 0;
        int j = max - 1;
        int maxarea = 0;
        for (int n = 0; n < max; n++) {
            maxarea = Math.max(maxarea, (j-i)*Math.min(height[i],height[j]));
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return maxarea;
    }

The result is

image

Further optimization#

I found that during the process of moving the left and right pointers towards the center. If the height of the pointer after the move is lower than before, then there is no need to calculate the "water volume" because it must have decreased, just continue moving. So I used two flags to record and improve the execution speed of the code.
So, here we go

    public int maxArea(int[] height) {
        //Optimized two pointers
        int max = height.length;
        int i = 0;
        int j = max - 1;
        int maxarea = 0;
        //Two flags to indicate the two sides
        int maxHeightI = height[i];
        int maxHeightJ = height[j];
        //Record whether the last move was made by the left pointer (0) or the right pointer (1)
        int flag = 0;
        for (int n = 0; n < max; n++) {
            if (flag == 0) {
                if (height[i] < maxHeightI) {
                    i++;
                    continue;
                }else {
                    maxHeightI = height[i];
                }
            }
            if (flag == 1) {
                if (height[j] < maxHeightJ) {
                    j--;
                    continue;
                }else {
                    maxHeightJ = height[j];
                }
            }
            maxarea = Math.max(maxarea, (j-i)*Math.min(height[i],height[j]));
            if (height[i] < height[j]) {
                i++;
                flag = 0;
            } else {
                j--;
                flag = 1;
            }
        }
        return maxarea;

    }

The result is indeed effective
image

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.