云博
二刷leetcode 11 盛水最多的容器 (双指针解)

阅读量:(38) 您现在所在的位置: 首页 百宝箱 Leetcode 二刷leetcode 11 盛水最多的容器 (双指针解) 作者:慎独、
简介:二刷leetcode 11 盛水最多的容器 (双指针解),双指针+动态规划思想,由两端--->中间遍历

题目 : Leetcode 11. 盛水最多的容器 二刷 (中等)


原题:

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/container-with-most-water


解题思路:

这道题利用双指针+动态规划的思想很容易就可以解出。

1.分别设置一头head,一尾tail,分别从头尾两端往中间遍历。

2.当height[head] < height[tail]时,head += 1; 反之 tail -= 1

3.利用木桶效应原理,取板短的那一个计算面积。

4.利用动态规划思想,计算每次的面积与之前最大的面积进行比较,得出新的最大的面积

5.head > tail 表示比较结束,跳出循环


代码:

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 双指针,一头一尾,从两头开始比较
        lens = len(height)
        head = 0
        tail = lens-1
        max_area = (tail-head) * min(height[head],height[tail])
        while head < tail:
            if height[head] < height[tail]:
               head += 1
            else:
               tail -= 1
            max_area = max(max_area, min(height[head],height[tail])*(tail-head))
        return max_area

点赞一波

3

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器

 网站动态: