Leetcode 11. 盛最多水的容器
算法
发布于: 2021-12-30

心情糟糕,情绪崩溃,破防了,刷题!

本题首先需要理解题意,容器中的柱子占用面积不进行计算。由于柱子是否占用与空出面积是否进行计算有歧义,本题不应作为面试等场景题目。

暴力

暴力解决了。

当然 Case 超时不会通过,算法应该是正确的。

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0 || height.length == 1) return 0;

    int max = 0;
    for (int i = 0; i < height.length; i++) {
        int leftLineHeight = height[i];
        for (int j = i + 1; j < height.length; j++) {
            int rightLineHeight = height[j];
            int min = min(leftLineHeight, rightLineHeight);
            int tmp = (j - i) * min;
            if (tmp > max) max = tmp;
        }
    }

    return max;
}

public int max(int x, int y) {
    return x > y ? x : y;
}

public int min(int x, int y) {
    return x < y ? x : y;
}

}

双指针

基本思想:

对O(n)的算法写一下自己的理解,一开始两个指针一个指向开头一个指向结尾,此时容器的底是最大的,接下来随着指针向内移动,会造成容器的底变小,在这种情况下想要让容器盛水变多,就只有在容器的高上下功夫。 那我们该如何决策哪个指针移动呢?我们能够发现不管是左指针向右移动一位,还是右指针向左移动一位,容器的底都是一样的,都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大,就要使移动后的容器的高尽量大,所以我们选择指针所指的高较小的那个指针进行移动,这样我们就保留了容器较高的那条边,放弃了较小的那条边,以获得有更高的边的机会。

来自 leetcode @Alba

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0 || height.length == 1) return 0;

        int max = 0;
        int left = 0;
        int right = height.length - 1;

        while(left < right) {
            max = max(max, (right - left) * min(height[left], height[right]));
            if (height[left] > height[right]) --right;
            else ++left;
        }

        return max;
    }

    public int max(int x, int y) {
        return x > y ? x : y;
    }

    public int min(int x, int y) {
        return x < y ? x : y;
    }

}