[leetcode] 11. Container With Most Water

[leetcode] 11. Container With Most Water

Description

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 and n is at least 2.

分析

题目的意思是：有一堆柱子，现在要选两根柱子，使得围成的面积能够装的水最多。

一是两边往中间找，二是每次放弃最短的版。这么做的原因在于：从起点和终点开始找，宽度最大，这时每移动一次其中一个点，必然宽度变小。如此一来，想求最大，只有高度增长才有可能做到，去掉限制----短板，即放弃高度较小的点。本质上是一种贪心的算法，如果没有想到从两头向中间遍历，这道题就有点麻烦。

代码

class Solution {public: int maxArea(vector& height) { int low=0; int high=height.size()-1; int max_area=0; while(low

参考文献

​​[编程题]container-with-most-water​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。