注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
刚开始刷leetcode,第一次遇到这种问题debug好久没弄出来,求助下,求高人指点,不胜感激 TT
我把 题目 测试数据 两地输出 解题思路 代码 都放到下面啦,也欢迎大家一起讨论~
题目:
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.
测试数据:
[68,113,143,194,176,62,158,162,103,75,104,179,189,150,151,180,76,158,158,19,198,42,119,13,127,158,193,59,146,80,41,15,193,184,161,121,198,71,83,102,146,139,33,135,89,184,115,117,142,25,136,93,67,7,106,146,165,100,6,64,180,47,31,125,183,192,46,182,63,129,36,161,68,69,96,110,54,164,27,148,189,116,41,9,123,100,155,89,152,113,153,84,160,184,9,144,128,55,78,143]
本地输出(正确答案):
16560
网站输出:
13871
解题思路:
先把数据找出金字塔形状来,即从左到最大值为单调递增,从右到最大值也为单调递增(可证明正确答案在其中选出)。然后再两边向中间压缩找正确答案。复杂度O(n)吧。
附代码:
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
static int maxArea(vector<int> &height) {
vector<int> hv1, lv1, hv2, lv2;
int nSize=static_cast<int>(height.size()), m1=0, m2=0;
if(nSize<=1)
return 0;
for(int i=0; i<nSize; i++){
if(height.at(i)>m1){
m1=height.at(i);
hv1.push_back(m1);
lv1.push_back(i);
}
if(height.at(nSize-1-i)>m2){
m2=height.at(nSize-1-i);
hv2.push_back(m2);
lv2.push_back(nSize-1-i);
}
if(m1==m2)
break;
}
/*
for(int i=0; i<static_cast<int>(hv1.size()); i++){
cout<<hv1.at(i)<<" ";
}
cout<<" @@ ";
for(int i=static_cast<int>(hv2.size())-1; i>=0; i--){
cout<<hv2.at(i)<<" ";
}
cout<<"."<<endl;
*/
int ans=0, i=0, j=0, s1=static_cast<int>(hv1.size()), s2=static_cast<int>(hv2.size());
for(; i<s1; i++){
//cout<<":"<<i<<" "<<s1<<endl;
for(; j<s2; j++){
//cout<<":"<<j<<" "<<s2<<endl;
if(hv1.at(i)>hv2.at(j)){
int area=hv2.at(j)*(lv2.at(j)-lv1.at(i));
if(area>ans)
ans=area;
//cout<<hv1[i]<<" "<<lv1[i]<<" "<<hv2[j]<<" "<<lv2[j]<<" :"<<area<<" ,"<<ans<<endl;
}
else{
int area=hv1.at(i)*(lv2.at(j)-lv1.at(i));
if(area>ans)
ans=area;
//cout<<hv1[i]<<" "<<lv1[i]<<" "<<hv2[j]<<" "<<lv2[j]<<" :"<<area<<" ,"<<ans<<endl;
break;
}
}
}
return ans;
}
};
------------------------------
代码写的不好看还望见谅。。 ><
再次感谢大家的帮助。 |