Promise Eclipse Mxnet excel spring post autocomplete js获取焦点事件 matlab读取dat文件 bootstrap图表 hadoop源码 查看kafka消费情况 idea大小写转换快捷键 java常用的包 python正则表达式 python类 python入门教程 python的str python创建数据库 javaindexof java函数 java运行环境配置 java设置 java手册 java结束线程 java基础框架 java配置文件 linux中sudo tftpd64 iphone滚动截屏 js判断字符串相等 dvwa安装教程 eclipse中文版下载 JScodeblocks汉化包 selinux关闭 小洛快跑 小票打印 英雄联盟设置 计划任务软件 sai怎么导入图片
当前位置: 首页 > 学习教程  > 编程语言

算法拉胯之旅

2020/10/8 20:07:23 文章标签:

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

LeetCode

11. 盛最多水的容器

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

在这里插入图片描述

示例:
输入:[1,8,6,2,5,4,8,3,7]
输出:49

题解

双指针法
两个指针分别指向左右两端,每次水的容量为两个指针指向的数字中较小值∗指针之间的距离
每次记录下当次计算得的容量,移动指向数字较小的那个指针,向中间靠拢,计算得容量,若比原来的大则覆盖,否则保持原来的容量。

对于左右指针相等的情况,因为此时左右指针都是“瓶颈”,无论移动哪一个,因为x轴方向的长度变小,移动之后的计算的面积一定减小,故应该两个指针同时移动,而代码实现时任意移动一边的指针即可。

用到algorithm中的min()和max()函数。

class Solution {
public:
	// 双指针法
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int area = 0;
        while (left < right) {
            int temp = min(height[left], height[right]) * (right - left);
            area = max(area, temp);
            // if (area < min(height[left], height[right]) * (right - left))
            //     area = min(height[left], height[right]) * (right - left);

            if (height[left] > height[right])
                right--;
            else if (height[left] <= height[right])
                left++;
        }
        return area;
    }
};

时间复杂度:O(n),向量中每个元素最多访问一次;
空间复杂度:O(1),额外使用常数级别的空间。


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

附件下载

上一篇:vscode中注释快捷键

下一篇:魔术方法

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?