11. 盛最多水的容器

张伦聪zhangluncong

发布于 2022-10-26 17:47:14

1110

发布于 2022-10-26 17:47:14

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。画 n 条垂直线，使得垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

注意：你不能倾斜容器，n 至少是2。

解：可以写2个循环进行暴力拆解，时间复杂度o(n^2)，通不过。所以需要加2个指针，关键是临界点height[left] < height[right]需要往哪边移动，时间复杂度o(n)。

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-04-23，如有侵权请联系 cloudcommunity@tencent.com 删除

容器