leetcode 11 Container With Most Water

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

题目地址:leetcode Container With Most Water

题目大意: 给定n个数a1~an,代表垂直x轴的线的高度。求任意两条线之间所能装水的最大容积。容积的计算方式为 min(ai,aj) * (j – i) ,  i < j

思路:

简单的做法是直接枚举起点i和终点j,然后计算一次min(ai,aj) * (j – i),取最大,这样复杂度O(n^2)

更好的做法是双指针,这样可以达到O(n).

一开始l和r分别指向首尾,即l = 0, r = len(a) – 1,  然后计算容积。 接着若a[l] < a[r] 则 l++ 否则 r–

为啥是对的? 看看公式min(ai,aj) * (j – i) ,  若 a[l] < a[r],只能通过增加二者中较小的a[l]来增加面积,因为j – i已经是目前能达到的最大值了。

C++

Java

Python

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 11 Container With Most Water
本文地址:https://www.hrwhisper.me/leetcode-container-with-most-water/

打赏一杯咖啡钱呗

Leetcode , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *