Leetcode.11 Container with Most Water

时间:2023-01-09 21:55:47

问题描述:

Given n non-negative integers a1a2, ..., an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) 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.

 

我的思路:

寻找两条边,这两条边满足这样的条件:两条边和x轴围成的容器能够容纳最多的水,返回最大的容水量。

最大的容水量会受最短的边的限制,所以我们可以从x轴最长开始,即坐标为0, 和坐标为vector.size()-1之间围成的容器,选择最短的边移动,因为长的边会给我们提供更大的余地。

容量的计算为: (right - left) * min(height[left], height[right])

时间复杂度为O(n)

 

代码:

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