Leetcode Study Day 14

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

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

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:


Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:

Input: height = [1,1]
Output: 1
 

Constraints:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

My solution

My solution is using the two pointers method. As what we want is the maximum water we could have, we need to find the height and the width. The height is determined by the lower height of two lines, while the width is the distance between two lines. Therefore, we use two pointers to find the maximum water. The left pointer starts from the leftmost line and the right pointer starts from the rightmost line. We find the lower height between them, times the width between them. If the result is greater than the current maxWater, we replace it. If the left pointer is the shorter one, we move to the next height, whearas we move the right pointer to left. We repeat the process until the two pointers meet each other.

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