11. Container With Most Water

Problem

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

Approach

• Tham lam
• maxArea = (r-l) * min(height[l], height[r])
• Trường hợp height[l] <= height[r]: cho con trỏ K = l+1, tăng k++ cho đến khi tìm vị trí đầu tiên mà
  height[k] > height[l]. Tại sao cần tìm k (height[k] > height[l]), mà bỏ qua các số i trong đoạn (l, k) (height[i] <= height[l])?
  Bời vì với các số i trong đoạn (l, k) ta có area1 = (r-i) * min(height[i], height[r])
  Và area trong đoạn [l, k] là area2 = (r-l) * min(height[l], height[r])
  và vì (r-i) <= (r-l) (i > l) và height[i] <= height[l] cho nên area1 trong đoạn (i, k)
  sẽ nhỏ hơn area2 trong đoạn [l, k];
• Tương tự trường hợp height[l] > height[r]:

Implementation

class Solution {
    public int maxArea(int[] height) {
        int l = 0; int r = height.length - 1;

        int maxWater = 0;
        while (l < r) {
            maxWater = Math.max(maxWater, (r-l) * Math.min(height[l], height[r]));
            if (height[l] <= height[r]) {
                int k = l+1; // index dau tien height[k] > height[l]
                while (k < r && height[k] <= height[l]) {
                    k++;
                }
                l = k;
            } else {
                int k = r-1; // index dau tien height[k] > height[r]
                while (l < k && height[k] <= height[r]) {
                    k--;
                }
                r = k;
            }
        }
        return maxWater;
    }
}