登录
  • #刷题
  • #leetcode

本地输出和网站输出不同:Container With Most Water

see_world
1236
7
刚开始刷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<<" "<<lv1<<" "<<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<<" "<<lv1<<" "<<hv2[j]<<" "<<lv2[j]<<" :"<<area<<" ,"<<ans<<endl;

break;

}

}

}

return ans;

}

};

------------------------------

代码写的不好看还望见谅。。 ><

再次感谢大家的帮助。
7条回复
热度排序

发表回复