LeetCode: Container With Most Water 题解

Given n non-negative
integers a1a2,
..., an, where each represents a point at coordinate
(iai). n vertical lines
are drawn such that the two endpoints of line i is at
(iai) 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.

贪心策略:两端设置围栏,无论如何注水,水只要不超过其中较短的那一根围栏即可,中间的柱子可以忽略。

相继缩短距离,较短一端的柱子换成向里的一根。

例如: height[left] <= height[right] :  left =
left+1;

        反之, right = right-1;


 1 class Solution {
2 public:
3 int maxArea(vector<int> &height) {
4 int ans=0,left=0,right=height.size()-1,contain;
5 while(left<right)
6 {
7 contain = (right-left)*min(height[right],height[left]);
8 ans = max(contain, ans);
9 height[left]<=height[right]?left++:right--;
10 }
11 return ans;
12 }
13 };

LeetCode: Container With Most Water 题解,布布扣,bubuko.com

时间: 06-06

LeetCode: Container With Most Water 题解的相关文章

LeetCode &quot;Container With Most Water&quot; - GREEDY?

O(n^2) is a naive solution. As rule of thumb, there must be O(n) soluion. Yes - Greedy. We assume widest container contains the most water, greedily, but it is possible that we have higher heights with narrower range, so we proceed. Of course we disg

#LeetCode# Container With Most Water (todo)

描述: 实现1 -- 求所有可能的值,O(N^2),超时了(因为超时没有跑所有的测试用例,所以不确定还有没有其他问题) 代码: 1 def maxArea(self, height): 2 tmp = len(height) 3 if tmp == 0 or tmp == 1: return 0 4 if tmp == 2: return abs(height[1] - height[0]) 5 6 minus_lst = [height[i] - height[i-1] for i in ra

LeetCode: Container With Most Water 解题报告

Container With Most WaterGiven 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 wit

[leetcode]Container With Most Water @ Python

原题地址:https://oj.leetcode.com/problems/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) an

[LeetCode]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 containe

[LeetCode] 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 containe

leetcode&mdash;&mdash;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 contai

leetcode——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 containe

Leetcode: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 containe