leetcode 11

题目大意,给n个点,在一个数轴上。每个点对x轴作垂线,找出由两条垂线和X轴组成的一个“容器”的装的水面积最大。就是两条垂线较小的高度*两垂线高度的面积最大。 1、暴力做法 两两遍历。显然是会超时的 2、思路一 从左到右,找出以每一个点所在的垂线作为较矮的高度时候的最大面积,把每个点的垂线作为最大面积一一比较即可。也就是一个点分别往左扫和往右扫。

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let maxarea = 0
    const length = height.length;
    for (let i = 0;i < length;i++){
        let leftarea = 0,rightarea = 0,lj = 0,rj = length - 1;
        while(lj < i){
            if (height[lj] >= height[i]){
            //往左扫到那条边比原来基准边大就可以停止扫了,因为再往左也没意义了
                leftarea = (i - lj) *  height[i];
                break;
            }
            lj ++;
        }
        while(rj > i){
            if (height[rj] >= height[i]){
            //同理
                rightarea = (rj - i) *  height[i];
                break;
            }
            rj --;
        }
        maxarea = Math.max(leftarea,rightarea,maxarea)
    }
    return maxarea
};

这样的效率虽然比暴力好一点能够通工leetcode的测评,但是效率还是很低的,只超过了百分之5的人。思路一之所以效率低,是因为有些情况下我们是做了重复的工作的。例如我以高度为4为矮边去扫到了1条高度为3的边。但是因为4是矮,所以会忽略了3的那次。然而实际上可能以那条3为矮的边与4组成的结果是更优的,而我们要到下次遍历到高度为3的那条边时才会去计算,而且思路2的方法的向左向右扫是会有不必要的重合的

思路2。 我又换了一种思路: 左侧断点和右侧断点同时开始扫,左右分别用两个东西标记一下。如果左边的垂线高度小于右边的,则左边的标记往右一位(这样才能找出更大的);同理右边的垂线高度小于左边的,则右边

var maxArea2 = function(height) {
    let maxarea = 0
    const length = height.length;
    let left = 0,right = length - 1;
    while (left < right){
        let area = Math.min(height[left],height[right]) * (right - left);
        maxarea = Math.max(area,maxarea);
        if (height[left] < height[right]){
            left ++;
        }else{
            right --;
        }
    }
    return maxarea
};

这种算法就优于百分之80的了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 由浅至深了解webpack异步加载背后的原理

    1、module:我们源码目录中的每一个文件,在 webpack 中当作module来处理(webpack 原生不支持的文件类型,则通过 loader 来实现)...

    flytam
  • 3分钟掌握hook在typescript中的姿势

    useState如果初始值不是null/undefined的话,是具备类型推导能力的,根据传入的初始值推断出类型;初始值是 null/undefined的话则需...

    flytam
  • 由浅至深了解webpack异步加载背后的原理

    1、module:我们源码目录中的每一个文件,在 webpack 中当作module来处理(webpack 原生不支持的文件类型,则通过 loader 来实现)...

    flytam
  • 开发自己的TCGA数据库下载器就是怎么简单

    看到jimmy总结的如此有规律的下载地址链接,我尝试用python写几句脚本下载一下tcga数据。

    生信技能树
  • 网络编程懒人入门(四):快速理解TCP和UDP的差异

    对于即时通讯开者新手来说,在开始着手编写IM或消息推送系统的代码前,最头疼的问题莫过于到底该选TCP还是UDP作为传输层协议。本文延续《网络编程懒人入门》系列文...

    JackJiang
  • JavaUtil_08_StringUtil_commons-lang3 之 StringUtils

    1.【commons】字符串工具类——commons-lang3之StringUtils

    shirayner
  • Java遍历集合的几种方法分析(实现原理、算法性能、适用场合)

    Java语言中,提供了一套数据集合框架,其中定义了一些诸如List、Set等抽象数据类型,每个抽象数据类型的各个具体实现,底层又采用了不同的实现...

    Java团长
  • .NETer们,你真的应该了解下EF Core3.x了!

    技术文,带你了解关于EntityFrameworkCore3.x的那些事,本文共1493个字,阅读大约需要3分钟。文末福利不要错过哦!

    Enjoy233
  • 遍历 AccessibilityNodeInfo 报 StackOverflowError

    在使用 AccessibilityService 遍历包含 WebView 的 AccessibilityNodeInfo 时会在某些情况下必现 StackOv...

    他叫自己MR.张
  • 硬核干货来了!鹅厂前端工程师手把手教你实现热力图!

    ? 各位小伙伴们,还记得今年年初时我们推出的数据可视化组件吗?《助你开启“上帝视角” 数据可视化组件全新上线》。这些基于地图的数据可视化组件,以附加库的形式加...

    腾讯位置服务

扫码关注云+社区

领取腾讯云代金券