【优选算法】—Leetcode—11—— 盛最多水的容器

1.题目

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

2.解法⼀（暴⼒求解）（会超时）：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ret = 0;
        // 两层 for 枚举出所有可能出现的情况
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算容积，找出最⼤的那⼀个
                ret = max(ret, min(height[i], height[j]) * (j - i));
            }
        }
        return ret;
    }
};

3.解法⼆（对撞指针）：

 4.代码实现

1.C语言

int min(int a, int b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}
int max(int num1, int num2) {
    return (num1 > num2 ) ? num1 : num2;
}
int maxArea(int* height, int heightSize)
 {
    int left = 0, right = heightSize- 1, ret = 0;
        while (left < right) {
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            // 移动指针
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
}

2.C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left < right) {
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            // 移动指针
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
    }
};