物联网项目 k8s paypal vbscript jackson arm vue插件库 ios视频教程 jq去除空格 js对象添加元素 mysql分区表优劣分析 python练习 mysql事务 河南普通话报名入口 python字典添加 java求和 java实用教程 怎么看java版本 java编程语言 java获取当前年月 java集合转数组 java怎么使用 java路径 java多线程编程 linux装机 广告代码 linux解压tar navicat注册机 js日期格式化 惠普战99 pmbok第六版 桌面数字时钟 img写盘工具 粉碎文件工具 4k对齐是什么意思 fireworks序列号 德玛上单天赋 一键清除锁屏密码 ps怎么羽化图片边缘 谷歌浏览器xp版下载
当前位置: 首页 > 学习教程  > 编程语言

面试题-盛最多水的容器

2020/11/24 9:48:26 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

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

题目描述
给定 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。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

题解
之前写过一版 [这里],但图配的不好,现重新画一下。

求容器能够容纳水的最大值,其实就是求矩形的最大面积。
我们定义两个指针来代表两个柱子,之后两个指针指向的较小者向中间移动,每次移动之前计算一下当前的面积,并保存下来,等到两个指针相遇时(即两个指针都指向同一个柱子时),遍历结束。
怎么计算矩形面积呢?
比如这个数组:
[1,8,6,2,5,4,8,3,7]
下标1的值是8,下标8的值是7。通过值和下标这两个维度就可以计算矩形了。
在这里插入图片描述
将右边下标减去左边下标,得到矩形的宽度
再计算max(arr[1],arr[8])得到矩形的高度
有了长度和高度就可以得出面积了。

完整的幻灯片演示如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
每次比较左右指针,选择较小的那个向左/向右 移动
比如 左边的1比右边的7小,那么选择移动左边的1
如果每次都移动大的,那结果就不对了 如果每次移动大的,那就向上图那样,右指针不断往左移动,但是左指针一直没变化过,计算出的计算面积就是8。
在这里插入图片描述

时间复杂度:O(n)
空间复杂度:O(1)

java代码:

class Solution {
    public int maxArea(int[] height) {
        if(height==null) {
            return 0;
        }
        //定义两个指针,分为位于最左边和最右边
        int i = 0;
        int j = height.length-1;
        int res = 0;
        //两个指针不断像中间移动,每迭代一次都会计算矩形的最大面积
        while(i<j) {
            int tmp = Math.min(height[i],height[j]);
            res = Math.max(res,tmp*(j-i));
            if(height[i]<=height[j]) {
                ++i;
            } else {
                --j;
            }
        }
        return res;
    }
}

Python代码

class Solution(object):
    def maxArea(self, height):
        if not height:
            return 0
        # 定义两个指针,分为位于最左边和最右边 
        i = 0
        j = len(height)-1
        res = 0
        # 两个指针不断像中间移动,每迭代一次都会计算矩形的最大面积
        while i<j:
            tmp = min(height[i],height[j])
            res = max(res,tmp*(j-i))
            if height[i]<=height[j]:
                i += 1
            else:
                j -= 1
        return res
func maxArea(a []int) int {
    n := len(a)
 
    if n < 2 {
        return 0
    }
 
    if n == 2 {
        return min(a[1], a[0])
    }
 
    max := min(a[n - 1], a[0]) * (n - 1)
 
    i := 0
    j := n - 1
 
    for i < j  {
        if a[i] < a[j] {
            i++
        }else {
            j--
        }
 
        area := min(a[i], a[j]) * (j - i)
        if area > max {
            max = area
        }
    }
 
    return max
}
 
func min(x, y int) int {
    if x < y {
        return x
    }
 
    return y
}

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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?