11. Container With Most Water
in LeetCode with 0 comment

11. Container With Most Water

in LeetCode with 0 comment

leetcode 11.盛最多水的容器

给定n个非负整数a1,a2,...,an,其中每个代表一个点坐标(i,ai)。

n个垂直线段例如线段的两个端点在(i,ai)和(i,0)。

找到两个线段,与x轴形成一个容器,使其包含最多的水。

备注:你不必倾倒容器。

mark

暴力

$O(n^2)$的复杂度。

class Solution {
public:
    int maxArea(vector<int>& height) {        //暴力写一个先
        int maxWater = 0,dataSize = height.size();
        for (int i = 0; i < dataSize; i++) {
            for (int j = i + 1; j < dataSize; j++) {
                maxWater = max(maxWater, min(height[i], height[j])*abs(i-j));
            }
        }
        return maxWater;
    }
};

肯定时间会超限

双指针法

O(n)的复杂度。

保持两个指针i,j,分别指向长度数组的首尾。

这个想法的基础是,如果i的长度小于j,无论如何移动j,短板在i,不可能找到比当前记录的area更大的值了,只能通过移动i来找到新的可能的更大面积。

class Solution { //传说中的左右指针,
public:
    int maxArea(vector<int>& height) {
        if (height.size() < 2)return 0;
        int i = 0, j = height.size() - 1;
        int maxWater = 0;
        while (i < j) {
            maxWater = max(maxWater, min(height[i], height[j])*abs(i - j));
            if (height[i] < height[j]) i++;
            else j--;
        }
        return maxWater;
    }
};
Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号