leetcode11--Container with most water

leetcode11--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.

解法

这个我最先想到的是比较笨的方法,即遍历每个柱子,算出这个柱子对应的能存的最多的水,然后更新最多的水,但是结果超时了

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        final_max = 0
        cur_max = 0
        
        for i in range(len(height)):
            for j in range(i+1, len(height)):       
                temp = min(height[i], height[j])*(j-i)
                cur_max = max(cur_max, temp)
            final_max = max(final_max, cur_max)
        return final_max
            


后来想了一想可以用前后指针的办法来做

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        water = 0
        i = 0
        j = len(height)-1
        while(i<j):
            min_h = min(height[i], height[j])
            water = max(min_h*(j-i), water)
            
            # 当没有这个高的时候就pass掉,往前进,停一下的时候已经到了一个更高的地方了
            while(height[i]<=min_h and i<j):  
                i += 1
            # 另外一头也做类似的操作
            while(height[j]<=min_h and i<j):
                j -= 1
        return water
                
            
                        

用c++来写的话是

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

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦