Leetcode——11. Container With Most Water

1. 概述

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 and n is at least 2.

题意是说在给定的一个数组中，将数组的下标作为转换坐标的X轴，数组下标对应的值为Y轴。在这样的情况下求取两个元素组成的长方形面积最大。

解题思路

（1）暴力搜索

也就是每种情况都去遍历一遍，肯定能找到一个最优解，但是这样的方式很暴力（O(N^2)），直接导致gg

显然这样的方式是不能使用的。

（2）面积最大时条件

通过分析面积最大时的条件，可以知道寻找到的两个数应该尽量的大，而且他们的距离应该尽量大。因而在搜索的策略上就选择：从数组的前端和末尾开始搜索；在每次搜索的过程中记录面积最大值，两边沿着数组元素大的方向搜索。原理就如下图所示

2. 编码

class Solution { public: int maxArea(vector<int>& height) { int len(height.size()); //容器的大小 int high(0); //得到的长方体的高度 if(1==len || 0==len) return 0; if(2 == len) { high = min(height[0], height[1]); return high; } int area(0); //最大的面积 //方法2，O(N) int left(0), right(len-1); while(left < right) { area = max(area, min(height[left], height[right])*(right-left)); if(height[left] < height[right]) ++left; else --right; } return area; } }; 性能