11.盛最多水的容器

简介: 11.盛最多水的容器

11.盛最多水的容器

寻找盛水面积最大的两条线,盛水面积 = 两条线的距离 *  两条线中较短的那条的高


1.暴力 (超时)

两层循环计算所有可能的面积,时间复杂度O(n^2),超时

 

2.双指针法:

思路是从左右两端开始移动,每次移动较短的那条。因为面积 = 距离 * min(左高度,右高度)。移动时距离减少,只有min(左高度,右高度)增加才可能让面积变大,而min()是由较小的数决定的,所以只有

较小的数改变,min()才会改变。从而面积才可能更大。

证明略。

 

时间复杂度O(n)

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


相关文章
|
7月前
|
存储 容器
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
LeetCode刷题---11. 盛最多水的容器(双指针-对撞指针)
|
算法 容器
【算法专题突破】双指针 - 盛最多水的容器(4)
【算法专题突破】双指针 - 盛最多水的容器(4)
44 0
|
算法 测试技术 容器
【算法挨揍日记】day02——双指针算法_快乐数、盛最多水的容器
题目: 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为:
64 0
|
6月前
|
算法 测试技术 程序员
力扣经典150题解析之二十八:盛最多水的容器
力扣经典150题解析之二十八:盛最多水的容器
53 0
|
7月前
|
容器
11. 盛最多水的容器
11. 盛最多水的容器
38 1
|
6月前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
|
7月前
|
容器
leetcode代码记录(盛最多水的容器
leetcode代码记录(盛最多水的容器
31 1
|
7月前
|
算法 容器
【优选算法】—Leetcode—11—— 盛最多水的容器
【优选算法】—Leetcode—11—— 盛最多水的容器
|
7月前
|
容器
【力扣】11. 盛最多水的容器
【力扣】11. 盛最多水的容器
|
7月前
|
容器
11.盛最多水的容器
11.盛最多水的容器
44 0