Leetcode 11：Container With Most Water

Description

Difficulty: Medium

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:
1
2
3
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:
1
2
Input: height = [1,1]
Output: 1
Example 3:
1
2
Input: height = [4,3,2,1,4]
Output: 16
Example 4:
1
2
Input: height = [1,2,1]
Output: 2
Constraints:

n == height.length

2 <= n <= 105

0 <= height[i] <= 104

容器的体积等于底×高，底等于x轴的长度，高是两边柱子中短的一根的长度，因此这道题可以用双指针从最左最右开始一点点往中间走寻找最高值。

示例：

[1,8,6,2,5,4,8,3,7]

8 * 1 = 8
7 * 7 = 49
6 * 3 = 18
5 * 8 = 40
3 * 4 = 12
2 * 5 = 10
1 * 2 = 2

Code:

class Solution {
    public int maxArea(int[] height) {
        int len = height.length;
        int width = len -1;
        
        int i=0; //first 
        int j=len-1; // last 
        int out = 0;
        int p1, p2;
        
        while (i<j){
            // it's important to set the updated value of p1 and p2 here
            p1 = height[i];
            p2 = height[j];
            out = Math.max(out, width * (p1>=p2 ? p2 : p1));
            
            // we change the position of shorter column and keep the longer one
            if(p1>p2){
                j -= 1;
                width--;
            } else if(p1<p2){
                i += 1;
                width--;
            } else { // if equal, we move both pointers
                j -= 1;
                i += 1;
                width -= 2;
            }            
        }        
        return out;             
    }
}

Summary

pointer, pointer, pointer!

总之希望自己能坚持下去，每周记录分享几道有趣的题和解法。也欢迎大家留言讨论补充(●’◡’●)