前言
这题非要说贪心的话也算是吧，不过最主要的特征还是双指针。LC的题好像不少都是扔倆头尾指针然后遍历一遍完事儿的。这道题倒是“短板效应”的不错体现了。
题目
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.
思路
图片看不清楚的话可右键复制链接转到图床再看。
代码
class Solution {
public:
int maxArea(vector<int>& height) {
int first = ;
int end = height.size() - ;
int result = INT_MIN;
while (first < end)
{
int width = end - first;
int board = height[end]<height[first]?height[end]:height[first];
int area = board*width;
result = result>area?result:area;
if (height[first] <= height[end])
first++;
else
end--;
}
return result;
}
};