【数据结构和算法】LeetCode 11. 盛最多水的容器

截止到目前我已经写了 600多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

【数据结构和算法】LeetCode 11. 盛最多水的容器

B站视频

1，以当前柱子为桶的高度，分别从两边查找

public int maxArea(int[] height) {
    int maxAre = 0;// 保存最大值
    int left = 0;
    int right = 0;
    int length = height.length;
    //以当前柱子为桶的左边界开始查找
    while (left < length) {
        // 从右边开始查找第一个不小于当前柱子的高度
        right = length - 1;
        while (left < right) {
            if (height[left] > height[right]) {
                right--;
            } else
                break;
        }

        //计算围成的面积
        int are = height[left] * (right - left);
        maxAre = Math.max(maxAre, are);
        left++;
    }

    right = length - 1;
    //以当前柱子为桶的右边界开始查找
    while (right > 0) {
        // 从左边开始查找第一个不小于当前柱子的高度
        left = 0;
        while (left < right) {
            if (height[right] > height[left]) {
                left++;
            } else
                break;
        }

        //计算围成的面积
        int are = height[right] * (right - left);
        maxAre = Math.max(maxAre, are);
        right--;
    }
    return maxAre;
}

2，双指针

public int maxArea(int[] height) {
    int maxAre = 0;// 保存最大值
    int left = 0;
    int right = height.length - 1;
    while (left < right) {
        maxAre = Math.max(maxAre, (right - left)
                * Math.min(height[left], height[right]));
        // 矮的柱子往中间靠
        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return maxAre;
}

3，双指针优化

public int maxArea(int[] height) {
    int maxAre = 0;// 保存最大值
    int left = 0;
    int right = height.length - 1;
    while (left < right) {
        int minHeight = Math.min(height[left], height[right]);
        maxAre = Math.max(maxAre, (right - left) * minHeight);
        // 如果两个柱子往中间靠的时候，有更短的或一样高的，直接跳过
        while (left < right && height[left] <= minHeight)
            left++;
        while (left < right && height[right] <= minHeight)
            right--;
    }
    return maxAre;
}