LeetCode: 11. Container With Most Water

题目描述

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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

大意是：给定n个非负整数 a1, a2, …, an, 代表坐标上的点 (i, ai). n 个（i, ai）到 (i ,0) 构成竖直的线。请找出两条线，使其和x轴一起组成的容器能容纳最多的水。保证 n 最小为2。

解题思路

用两根指针（i 和 j），分别从两边开始遍历。容器容纳的水的最大高度实际为 min(height[i],height[j])。如果 height[i]<height[j] 那么容器的容量受 i 的影响，因此我们让 i++，寻找增大容量的 i。(如果让 j-- 的话，容器的底变窄了，而高又不可能超过 height[i], 因此容量一定会减少。) height[i]>height[j] 同理。

AC 代码

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