首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode 11

leetcode 11

作者头像
flytam
发布2020-01-14 16:56:28
3360
发布2020-01-14 16:56:28
举报
这里写图片描述
这里写图片描述

题目大意,给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的了。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档