【LeetCode with Python】 11. Container With Most Water

题目

原题页面:https://leetcode.com/problems/container-with-most-water/
本文地址:http://leetcode.xnerv.wang/container-with-most-water/
题目类型:Array, Two Pointers
难度评价:Medium
类似题目:(H) Trapping Rain 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.


分析

贪婪法的思想,用两个指针从数组的左边和右边开始,向中间搜索。依据的理由有两点:
1、因为一开始底边长就已经是最大,两个指针向中间移动的时候,底边长只会变短,因此如果此时面积要变大的话,只能是两条高中的最短者比移动前的最短高更高,否则就无需考察,直接continue到下一次的循环。
2、因此,每次选择移动左指针还是右指针,优先选择当前高度最短的那个,以期寻找到更高的边。如果此时选择移动当前高度最高的那个,就有可能跳过了最优解。


代码

class Solution:
    # @return an integer
    def maxArea(self, height):
        len_height = len(height)
        if 1 == len_height:
            return 0
        max_area = 0
        left_index = 0
        right_index = len_height - 1
        while left_index < right_index:
            if height[left_index] < height[right_index]:
                area = (right_index - left_index) * height[left_index]
                left_index += 1
            else:
                area = (right_index - left_index) * height[right_index]
                right_index -= 1
            if area > max_area:
                    max_area = area
        return max_area

results matching ""

    No results matching ""