Leetcode: Container With Most Water

本文主要是介绍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 container, such that the container contains the most water.

Note: You may not slant the container.

思路分析：
给定数组A[]，求直线((i, 0), (i, A[i]))、((j, 0), (j, A[j]))和X轴围成的体积重最多能装多少水。这个装水的多少是由abs(i - j)和min(A[i], A[j])共同决定的。两者的积越大，则能装的水越多。
所以我们先让abs(i - j)取最大值，通过左右两个指针，逐渐移动，逐步调整min(A[i], A[j])和abs(i - j)得到最大值。

C++参考代码：

class Solution
{
public:int maxArea(vector<int>& height){int count = int(height.size());if (count == 0) return 0;int left = 0;int right = count - 1;int maxArea = 0;//最大面积int curArea = 0;//当前面积while (right > left){curArea = min(height[left], height[right]) * (right - left);if (curArea > maxArea) maxArea = curArea;if (height[left] > height[right]) --right;else ++left;}return maxArea;}
};

这篇关于Leetcode: Container With Most Water的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---