题目
You are given an integer array of length . There are vertical lines drawn such that the two endpoints of the line are and .heightnnith(i, 0)(i, height[i])
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
答案
class Solution {
public:
typedef pair<int, int> pii;
int maxArea(vector<int>& height) {
vector<pii> tmp;
int size = height.size();
tmp.reserve(size);
for (int i = 0; i < size; i++) {
tmp.push_back(make_pair(height[i], i));
}
sort(tmp.begin(), tmp.end(), [](const pii& a, const pii& b) {
return a.first > b.first;
});
int minloc=tmp.front().second;
int maxloc=minloc;
int result=0;
for(int i=0;i<size;i++){
result=max(
max(
abs(minloc-tmp[i].second),
abs(maxloc-tmp[i].second)
)*tmp[i].first,
result
);
minloc=min(tmp[i].second,minloc);
maxloc=max(tmp[i].second,maxloc);
}
return result;
}
};
思路
- 先将柱子从高到矮排序
- 从高到矮依次寻找，保留当前遇到的最左侧位置和最右侧位置。
- 遇到的新的一个柱子相对于前一个柱子较矮，因此能在限制前面所有柱子高度的前提下，不受后面柱子的影响计算局部最优解。
- 最后得出的为全局最优解。
答案2
class Solution {
public:
typedef pair<int, int> pii;
int maxArea(vector<int>& height) {
int size=height.size();
int lp=0;
int rp=size-1;
int result=0;
while(lp!=rp){
result=max(
result,(min(height[lp],height[rp])*(rp-lp))
);
if(height[lp]<height[rp])lp++;
else rp--;
}
return result;
}
};
思路2
- 定义
f(i,j)为i到j的最大容积，g(i,j)=abs(height[i]-height[j])*(j-i),f(i,j)所有g的最大值。 - 假设
height[i]<=height[j],如果height[i+1]>=height[i],则f(i,j)=max(g(i,j),f(i+1,j)),g(i,j)<=g(i+1,j)。如果hieght[i+1]<height[i],则f(i,j)=max(g(i,j),f(i+1,j)),g(i,j)>g(i+1,j)。以上两种情况可以归纳为f(i,j)=max(g(i,j),f(i+1,j))。