题目
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.
分析
题意是有个高度数组,就相当于隔板的高度,求数组中任意两隔板间盛水的最大量。隔板间的距离与较低隔
板的高度乘积即为盛水的容量。
AC代码
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
if (height.empty())
return 0;
int maxCapacity = 0;
size_t lhs = 0, rhs = height.size() - 1;
while (lhs < rhs)
{
int capacity = (rhs - lhs) * min(height[lhs], height[rhs]);
if (capacity > maxCapacity)
{
maxCapacity = capacity;
}
if (height[lhs] < height[rhs])
++lhs;
else
--rhs;
}//while
return maxCapacity;
}
};
int main()
{
Solution s;
vector<int> v = { 1, 2, 3, 4 };
cout << s.maxArea(v) << endl;
system("pause");
return 0;
}