LeetCode(11) Container With Most Water

时间:2023-06-13 10:21:32

题目

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;
}

GitHub测试程序源码