一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 590|回复: 7
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
see_world 发表于 2015-3-6 19:13:13 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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;
    }
};



------------------------------
代码写的不好看还望见谅。。 ><
再次感谢大家的帮助。
stellari 发表于 2015-3-7 13:19:44 | 显示全部楼层
主要原因是第一个循环中的
if (m1 == m2) break;
这句。

我想你的本意是让“hv1和hv2的顶部同时为中间的金字塔尖端时停止”。但是,m1 == m2这个条件的意思则是“hv1和hv2的顶部值相同时停止”。因为这组数据中有大量的重复数据,所以在m1 = 143,m2 = 143就停止了,没法运行到 m1 = m2 = 198这个最大值。所以最后的结果是143 * 97 = 13871。而hv1中本该包含的194, 198和hv2中该出现的144, 184, 189, 192, 198都没有出现。自然不可能得出正确结果 184 * 90 = 16560。

综上。这段代码理论上来说是不可能得到16560的。我想,要么是你碰巧注释掉了m1 == m2这一句,要么是往代码中粘贴数据时,正好少粘贴了结尾的143,或者以其他方式忽略了这个数。你最好再仔细检查一遍。

还有,这段代码在最坏情况下不是O(n)。假如height中有这样的2n-1个数字:
n+1, n+2, n+3, n+4, ...., 2*n-1, 2*n, n-1, n-2, .... 3, 2, 1
那么由于前半单调增,后半单调减,hv1和hv2中会分别存放这个数组的前半和后半部分,各有n个数。且此时hv1中的最小数n+1也大于hv2中的最大数n-1。
所以在接下来的二重循环中,hv1 > hv2[j]会始终为真,也就是说else中的break将永远不能得到执行。在循环中又没有对i,j和s1,s2的增减操作。所以n x n = n^2次会被一次不差地执行完。因此,最差运行时间为O(n^2)。

你的思路方向是对的。但是这段代码的写法看起来并不能完美地反应出这一点。我建议你不要使用二重循环,而改为在一个while循环内使用两个指针(下标变量)。那样的话代码会显得更清晰。而且能够避免上面所说的问题。



补充内容 (2015-3-9 18:15):
二重循环的代码确实是O(n),之前的分析是不正确的,请见谅。

评分

3

查看全部评分

回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-3-7 17:53:15 | 显示全部楼层
你把static去掉试试。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| see_world 发表于 2015-3-9 10:34:35 | 显示全部楼层
Linzertorte 发表于 2015-3-7 17:53
你把static去掉试试。

首先感谢。
不过这个static是我自己在测试的时候加上的,网站上没有加。。
回复 支持 反对

使用道具 举报

 楼主| see_world 发表于 2015-3-9 10:37:42 | 显示全部楼层
stellari 发表于 2015-3-7 13:19
主要原因是第一个循环中的
if (m1 == m2) break;
这句。

sooo感谢,发现的确自己的思路有很不完善的地方。

我来改一下试试看吧,再次感谢~
回复 支持 反对

使用道具 举报

 楼主| see_world 发表于 2015-3-9 11:13:12 | 显示全部楼层
stellari 发表于 2015-3-7 13:19
主要原因是第一个循环中的
if (m1 == m2) break;
这句。

关于第一点,说得非常对,就是那句话的问题,而自己测试的时候的确少加了第二个143 orz

关于第二点,我的算法应该不会退化带O(n^2)的复杂度,应为两面都是单向向里面压缩的(i j 是之前定义的,我刚才用你给的数据测试了下)。不过你说得对,的确这么写不够明确,那一段我修改成了:
while(i<s1 && j<s2){
            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;
                j++;
            }
            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;
                i++;
            }
        }

提交的leetcode测试已通过,虽然效率好像不高,我到网上看看别人代码吧。

再次感谢! ^^
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-9 18:12:44 | 显示全部楼层
see_world 发表于 2015-3-9 11:13
关于第一点,说得非常对,就是那句话的问题,而自己测试的时候的确少加了第二个143 orz

关于第二点, ...

你说得对,确实是O(n)的。我是受了那个二重循环的误导。后面的while写法就好多了。

另外,其实没必要刻意去找hv1和hv2两个递增序列。这个算法可以直接用到原始序列上。这样,代码看起来会简单些,面试时写出来的压力也小些。
回复 支持 反对

使用道具 举报

 楼主| see_world 发表于 2015-3-10 09:19:33 | 显示全部楼层
stellari 发表于 2015-3-9 18:12
你说得对,确实是O(n)的。我是受了那个二重循环的误导。后面的while写法就好多了。

另外,其实没必要 ...

是啊,网上其他人也是这么做的,我居然没反应到这点。一开始想到金字塔之后就没绕出来,估计时间效率不高也跟这个有关吧。

再次感谢讨论!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 20:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表