容器最大容水量

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

• 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.

• 題目大意：给定n个非负整数a1，a2，......，an，他们每一个分别表示坐标上的一个点（i，ai）。绘制n条垂直于 x 轴的直线，第 i 条垂线的两个端点的坐标分别是（i，ai）和（i，0）。找出两条线，这两条线和 x 轴组成一个容器，使得这个容器能盛最多的水。

• 思路：假设n = 10，a[n] = {0，1，0，2，1，0，1，3，2，1}，按照题目要求绘制下图，从图中可以看出，当这两条线分别垂直于起点和终点时，这时宽度最大，这时每移动一次其中一个点，必然宽度变小。如此一来，想求最大，只有高度增长才有可能做到，所以每次（1）两边往中间找，（2）每次放弃最短的版，这是因为，去掉限制----短板，即放弃高度较小的点，就有可能会获得更高的高度，从而得到更大的容积。

  
  

• 代码：

#include<iostream>
#include<vector>
using namespace std;
int maxArea(vector<int> &height)
{
    int Max = 0,left = 0,right = height.size() - 1;
    while(left < right)
    {
        Max = max(Max, (right-left) * min(height[left], height[right]));
        height[left] < height[right] ? left++ : right--;
    }
    return Max;
}
int main()
{
    vector<int> height;
    for(int i = 0; i < 10; i++)
    {
        int h;
        cin >> h;
        height.push_back(h);
    }
    cout << maxArea(height) << endl;
    return 0;
}

运行结果：通过

• 以上。

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~