[LeetCode]11.Container With Most Water
【题目】
Givennnon-negative integersa1,a2, ...,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpoints of lineiis 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.
【分析一】
最直接的思路是暴力枚举法，枚举容器的两个边。O(n^2)。超时。
【代码一】
/*********************************
* 日期：2015-01-21
* 作者：SJF0115
* 题目: 11.Container With Most Water
* 网址：https://oj.leetcode.com/problems/container-with-most-water/
* 结果：Time Limit Exceeded
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int maxArea(vector<int> &height) {
int count = height.size();
if(count <= 1){
return 0;
}//if
int maxArea = 0;
// 左边界
for(int i = 0;i < count-1;++i){
// 右边界
for(int j = i+1;j < count;++j){
int area = (j - i) * min(height[i],height[j]);
maxArea = max(area,maxArea);
}//for
}//for
return maxArea;
}
};
int main(){
Solution solution;
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
vec.push_back(1);
vec.push_back(4);
vec.push_back(2);
int result = solution.maxArea(vec);
// 输出
cout<<result<<endl;
return 0;
}
【分析二】
当从两边向中间考虑时，面积 = 两端较小的高度×两边之间的宽度。
假定初始的盛水面积为area=0，如果左边的高度小于右边的高度，容器左边向右运动一位。同理，如果右边的高度小于左边的高度，则向左运动一位。
【代码二】
/*********************************
* 日期：2015-01-21
* 作者：SJF0115
* 题目: 11.Container With Most Water
* 网址：https://oj.leetcode.com/problems/container-with-most-water/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int maxArea(vector<int> &height) {
int count = height.size();
if(count <= 1){
return 0;
}//if
int maxArea = 0,area = 0;
// 二分查找变形
for(int i = 0,j = count-1;i < j;){
// 去掉低的一边
if(height[i] > height[j]){
area = (j - i) * height[j];
--j;
}//if
else{
area = (j - i) * height[i];
++i;
}//else
// 更新最大面积
if(area > maxArea){
maxArea = area;
}//if
}//for
return maxArea;
}
};
int main(){
Solution solution;
vector<int> vec;
vec.push_back(2);
vec.push_back(3);
vec.push_back(1);
vec.push_back(4);
vec.push_back(2);
int result = solution.maxArea(vec);
// 输出
cout<<result<<endl;
return 0;
}
【分析三】
当从两边向中间考虑时，面积 = 两端较小的高度×两边之间的宽度。
假定初始的盛水面积为area=0，如果左边的高度小于右边的高度，容器左边向右运动，直到找到一个比原先左边高度高的。
同理，如果右边的高度小于左边的高度，则向左运动，直到找到一个比原先右边高度高的。
【代码三】
class Solution {
public:
int maxArea(vector<int> &height) {
int count = height.size();
if(count <= 1){
return 0;
}//if
int index,maxArea = 0,area = 0;
// 二分查找变形
for(int i = 0,j = count-1;i < j;){
// 去掉低的一边
if(height[i] > height[j]){
area = (j - i) * height[j];
index = j;
// 向左移动,直到找到一个比height[index]高的
while(height[j] <= height[index]){
--j;
}//while
}//if
else{
area = (j - i) * height[i];
index = i;
// 向右移动,直到找到一个比height[index]高的
while(height[i] <= height[index]){
++i;
}//while
}//else
// 更新最大面积
if(area > maxArea){
maxArea = area;
}//if
}//for
return maxArea;
}
};【分析四】
构建结构体包含height和height在原数组中的位置
struct Node
{
int height;
int index;
};
对该结构体数组按照height的值递增排序，假设排序后的数组为vec.
假设f[i] 表示数组vec[i,i+1,…]内所有height按照原来的位置顺序排列好以后的最大水量
那么f[i-1]可以在O（1）时间内计算出来：因为vec[i-1].height 小于vec[i,i+1,…]内的所有height，所以以vec[i-1].index为边界的容器高度为vec[i-1].height，最大水量只需要分别计算vec[i,i+1,…]内按原始位置排列最前面和最后面的height，取两者的较大值。即下图中，黑色是最低的，要计算以黑色为边界的容器的最大水量，只需要分别和第一个和最后一个计算，去两者较大值
【代码四】
class Solution {
struct Node
{
int height;
int index;
Node(int h, int i):height(h),index(i){}
Node(){}
bool operator < (const Node &a)const
{
return height < a.height;
}
};
public:
int maxArea(vector<int> &height) {
int res = 0, n = height.size();
if(n <= 1)return 0;
vector<Node>vec(n);
for(int i = 0; i < n; i++)
{
vec[i].index = i;
vec[i].height = height[i];
}
sort(vec.begin(), vec.end());
int start = vec[n-1].index, end = start;//记录已经处理完的height的原始位置的左右端点
for(int i = n-2; i >= 0 ; i--)
{
start = min(start, vec[i].index);
end = max(end, vec[i].index);
res = max(res, max(vec[i].height*(vec[i].index - start), vec[i].height*(end - vec[i].index)));
}
return res;
}
};类似题目：