leetcode NO.11 盛最多水的容器 腾讯精选练习50

题目描述

第一想法就是时间复杂度为O（$n^2$n2）的暴力**，虽然我自己写也写的很磕绊就是了，辣鸡就是我！

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxarea = 0
        x1 = 0
        x2 = 0
        for i in height[0:len(height)-1]:
            x1 = x1 + 1
            x2 = x1
            for j in height[x1:len(height)]:
                x2 = x2 + 1
                if i <= j:
                    h = i
                else:
                    h = j
                w = x2 - x1
                area = h * w
                if area >= maxarea:
                    maxarea = area
        return maxarea

非常的傻批，因为一开始用下标循环，只知道从0开始不知道怎么从i开始就只能退而求其次直接循环里面的数了，然后用x1,x2记录宽度
实际上非常的简单用range（i：len(height)）就可以了，肥肠的easy

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        #寻找每对线段的面积，找最大值，时间复杂度O(n^2),超时
        max_area = 0
        for i in range(len(height)):
            for j in range(1, len(height)):
                 max_area = max(min(height[i], height[j])*(j-i), max_area)
        return max_area

就是短短几行就OJBK！

官方的双指针解法很精妙，感觉像贪心算法，特别是从两端开始收缩，就意味着一开始的宽度是最大的，依次比较左右两边的高度，把矮的板换掉，为什么要换矮的板，是因为只有往后搜索的板比这块矮的板高时才有可能比现在这两块板形成的面积大，因为宽度在搜索中时不断变小的，也就是说这种扫描的方法，每次都向着最优的组合去的，所以说有点像贪心算法。
我把官方解法的动图截了上来，大家看了有助理解

代码如下

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        right = len(height) - 1
        maxArea = 0
        while left < right:
            b = right - left
            if height[left] < height[right]:
                h = height[left]
                left += 1
            else:
                h = height[right]
                right -= 1
            area = b*h
            if maxArea < area:
                maxArea = area
        return maxArea