typora Jetbains全家桶 flash encoding pygame jtable Zeptojs Egret Engine Select2 vue开发 angular视频教程 查看oracle连接数 arraylist删除指定元素 idea全文搜索快捷键 python打开文件 python字典添加 python基础教程免费 python语言编程 python创建文件 java地址 jdbc连接mysql java输出数组 java输出当前时间 java调用接口 java调用方法 java文件复制 linux启动 java游戏开发教程 心理学与生活txt 电子书之家 按钮制作 俄罗斯方块java代码 隐藏虚拟键 cfqq网吧任务 fdisk下载 小工具 pr蒙版 vs2012中文旗舰版下载 拍照姿势的摆法女 mysql数据库恢复
当前位置: 首页 > 学习教程  > python

【Leetcode】11. 两数相加(Container With Most Water)

2021/2/6 22:21:37 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No11. 两数相加 题目 给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同…

No11. 两数相加

题目

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

说明:你不能倾斜容器。

示例 1

在这里插入图片描述

  • 输入:[1,8,6,2,5,4,8,3,7]
  • 输出:49
  • 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2

  • 输入:height = [1,1]
  • 输出:1

示例 3

  • 输入:height = [4,3,2,1,4]
  • 输出:16

示例 4

  • 输入:height = [1,2,1]
  • 输出:2

提示

  • n = height.length
  • 2 <= n <= 3 * 104
  • 0 <= height[i] <= 3 * 104

解题代码(Python3)

class Solution:
    def maxArea(self, height: List[int]) -> int:

        #新建数组集合
        heightSet = sorted(set(height),reverse = True)
        #新建数组下标索引字典
        heightDict = {x:[] for x in heightSet}
        #添加字典元素
        for i,x in enumerate(height):
            heightDict[x].append(i)

        #初始化
        result = 0 
        right = 0
        left = len(height) - 1

        #返回比较中的最大值 i代表heightSet中的索引下标
        for i in range(len(heightSet)):
            tempData = heightSet[i]
            tempList = heightDict[tempData]
            left = min(left,tempList[0])
            right = max(right,tempList[-1])
            result = max(result,tempData * (right - left))
        
        return result

思路:

新建表示容器高度的set,从地到高排列,然后利用dict构建每个高度所在的下标,循环遍历set,比较每个高度的容器的最大值和当前最大值,最终返回最大值。

复杂度分析:

  • 时间复杂度O(nlogn) 因为使用了列表的排序
  • 空间复杂度O(n)

运行结果:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000023.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?