<Data Structures/Algorithms> leetcode hot100 - 110.Container With Most Water

[LeetCode Hot 100] 110. Container With Most Water

Problem Link

This type of problem is frustrating because it often feels like the answer is just within reach, yet you can’t quite get it.

How to approach this? Consider two vertical lines. If the left line is taller than the right line, then if we choose either of these as the left boundary, the right one will always be limiting.

Look at the two endpoints of the array. If the left line is shorter, it doesn’t matter how tall the right line is; this is the “bottleneck effect.” Therefore, any container using the leftmost line as the left boundary cannot be the largest. In other words, the leftmost line can be “skipped.”

Next, calculate the container’s area, then move the left pointer rightward to the next line. For the new endpoints, apply the same logic: discard the shorter line. Repeat this process until the two pointers meet.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxVolume = 0;
        while(left < right){
            int curVolume = (right - left) * min(height[left], height[right]);
            maxVolume = max(maxVolume, curVolume);
            if(height[left] >= height[right]){
                right--;
            } else{
                left++;
            }
        }
        return maxVolume;
    }
};

中文原文

[LeetCode hot 100] 110. 盛水最多的容器

题目链接

最烦这种题，因为每次都感觉自己那么接近答案，就是做不出来，像个傻子一样。

怎样思考这个问题？首先我们从左往右看一看，假如有两根柱子，左边的柱子比右边的高，那么当选取这两个柱子之一作为左边的容器壁时，右边的柱子是一定会输的。

考虑数组的左右两个端点，假如左边的柱子更矮，那么右边的柱子无论再怎么高也没有用，这就是所谓的木桶效应。所以事实上以最左侧柱子为左端点的容器都不需要看了，因为不会有比现在更大的了。这也就是说，最左侧的柱子被“pass”了。

那么接下来就算一下这个容器的容量，然后把最左侧的柱子扔了，换第二个，也就是left指针右移。对于新的左右端点，运用同样的思路，排掉较短的那一根，如此循环直到左右端点相遇。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxVolume = 0;
        while(left < right){
            int curVolume = (right - left) * min(height[left], height[right]);
            maxVolume = max(maxVolume, curVolume);
            if(height[left] >= height[right]){
                right--;
            } else{
                left++;
            }
        }
        return maxVolume;
    }
};