每日leetcode–Container With Most Water

2,055次阅读

原题目:

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

盛水的多少由短板决定以及两个板之间的距离，木桶效应决定板的高度

class Solution {
public:
    int maxArea(vector& height) {
        int result=0;
        int lx=0;
        int rx=height.size()-1;
        if(rx<=0)
        {
            return 0;
        }
        
        while(lx<rx)
        {
            int tmp_area=(rx-lx)*min(height[lx],height[rx]);
     
            if(height[lx]<height[rx])             
            {                
                lx++;             
            }else             
            {                
                rx--;             
            }             
            if(tmp_area>result)
            {
                result=tmp_area;
            }
        }
        return result;
        
    }
};

发表于：leetcode

2016-04-18

# leetcode