首页 > 试题广场 >

盛水最多的容器

[编程题]盛水最多的容器
  • 热度指数:42851 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组height,长度为n,每个数代表坐标轴中的一个点的高度,height[i]是在第i点的高度,请问,从中选2个高度与x轴组成的容器最多能容纳多少水
1.你不能倾斜容器
2.当n小于2时,视为不能形成容器,请返回0
3.数据保证能容纳最多的水不会超过整形范围,即不会超过231-1

数据范围:


如输入的height为[1,7,3,2,4,5,8,2,7],那么如下图:


示例1

输入

[1,7,3,2,4,5,8,2,7]

输出

49
示例2

输入

[2,2]

输出

2
示例3

输入

[5,4,3,2,1,5]

输出

25
class Solution:
    def maxArea(self , height: List[int]) -> int:
        # write code here
        '''超时了'''
        # if len(height) < 2:
        #     return 0
        # left = 0
        # res = 0
        # while left < len(height) - 1:
        #     for right in range(left + 1, len(height)):
        #         mianji = min(height[left], height[right]) * (right - left)
        #         res = max(res,mianji)
        #     left = left + 1
        # return res
        '''双指针'''
        left = 0
        right = len(height) - 1
        res = 0
        while left < right:
            mianji = min(height[left], height[right])*(right - left)
            res = max(res, mianji)
            if height[left] < height[right]:
                left = left + 1
            else:
                right = right - 1
        return res

发表于 2025-02-23 23:27:16 回复(0)
class Solution:
    def maxArea(self , height: List[int]) -> int:
        l = len(height)
        # 特殊情况n<2
        if l < 2return 0
        left, right = 0, l-1
        # 记录容器的最大量
        ma = 0 
        while left < right:
        #right-left表示宽度,min(height[left],height[right])表示高度,木桶效应,以最低那个为准
            contain = (right-left) * min(height[left],height[right])
            ma = max(ma, contain)
            if height[left] < height[right]:
                left += 1
            else: right -=1
        return ma
发表于 2022-09-19 13:40:22 回复(0)