盛最多水的容器算法题解C/C++/JAVA/Python
  • 2019-12-22 14:38
  • 173
  • 0
  • 算法题解

题目:

给定 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

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/container-with-most-water

C解法:

int max(int a, int b)
{
    return a > b ? a : b;
}
int min(int a, int b)
{
    return a < b ? a : b;
}
int maxArea(int *height, int heightSize)
{
    int area = 0, l = 0, r = heightSize - 1;
    while (l < r)
    {
        area = max(area, min(height[l], height[r]) * (r - l));
        if (height[l] < height[r])
        {
            l++;
        }
        else
        {
            r--;
        }
    }
    return area;
}

C++解法:

class Solution
{
public:
    int maxArea(vector<int> &height)
    {
        int area = 0, l = 0, r = height.size() - 1;
        while (l < r)
        {
            area = max(area, min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
            {
                l++;
            }
            else
            {
                r--;
            }
        }
        return area;
    }
};

JAVA解法:

class Solution {
    public int maxArea(int[] height) {
        int area = 0, l = 0, r = height.length - 1;
        while (l < r) {
            area = Math.max(area, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return area;
    }
}

Python3解法:

class Solution(object):
    def maxArea(self, height):
        area, l, r = 0, 0, len(height)-1
        while l < r:
            area = max(area, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r += 1
        return area
共 0 条评论