LeetCode - 11. Container With Most Water

简介: 11. Container With Most Water  Problem's Link  ---------------------------------------------------------------------------- Mean:...

11. Container With Most Water 

Problem's Link

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

Mean: 

给你一个N条垂直于x轴的直线,从中找两条直线和x轴组成一个桶状容器,使得这个容器的容量最大.

analyse:

1.O(n^2)的做法就不说了,妥妥的超时.

for( int i = 0; i <n; ++ i)
    for( int j = i + 1; j <n; ++ j)
        ...

2.后来在上面方法的基础上加了一些剪枝,但复杂度还是O(n^2),也超时.

// Time Limit Exceeded
class Solution
{
public :
    int maxArea( vector < int >& height)
    {
        if( height . size() <= 1)
            return 0;
        vector < int > frontIdx;
        frontIdx . push_back( 0);
        auto ret = 0;
        for( auto i = 1; i < height . size(); ++ i)
        {
            for( auto idx: frontIdx)
            {
                ret = max( ret , min( height [ idx ], height [ i ]) *( i - idx));
            }
            auto endIdx =* frontIdx . rbegin();
            if( height [ i ] > height [ endIdx ])
                frontIdx . push_back( height [ i ]);
        }
        return ret;
    }
};

 3.后来看了discuss,看到这个做法,甚是巧妙.

proof:

The O(n) solution with proof by contradiction doesn't look intuitive enough to me. Before moving on, read the algorithm first if you don't know it yet.

Here's another way to see what happens in a matrix representation:

Draw a matrix where the row is the first line, and the column is the second line. For example, say n=6.

In the figures below, x means we don't need to compute the volume for that case: (1) On the diagonal, the two lines are overlapped; (2) The lower left triangle area of the matrix is symmetric to the upper right area.

We start by computing the volume at (1,6), denoted by o. Now if the left line is shorter than the right line, then all the elements left to (1,6) on the first row have smaller volume, so we don't need to compute those cases (crossed by ---).

  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x 
4 x x x x
5 x x x x x
6 x x x x x x

 Next we move the left line and compute (2,6). Now if the right line is shorter, all cases below(2,6) are eliminated.

  1 2 3 4 5 6
1 x ------- o
2 x x       o
3 x x x     |
4 x x x x   |
5 x x x x x |
6 x x x x x x

And no matter how this o path goes, we end up only need to find the max value on this path, which contains n-1 cases.

  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x
class Solution
{
public :
    int maxArea( vector < int >& height)
    {
        int si = height . size();
        int low = 0 , high = si - 1;
        int ret = 0;
        while( low < high)
        {
            ret = max( ret , min( height [ low ], height [ high ]) *( high - low));
            if( height [ low ] < height [ high ])
                ++ low;
            else
                -- high;
        }
        return ret;
    }
};

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-02-16-09.42
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
/*
// Time Limit Exceeded
class Solution
{
public:
   int maxArea(vector<int>& height)
   {
       if(height.size()<=1)
           return 0;
       vector<int> frontIdx;
       frontIdx.push_back(0);
       auto ret=0;
       for(auto i=1;i<height.size();++i)
       {
           for(auto idx:frontIdx)
           {
               ret=max(ret,min(height[idx],height[i])*(i-idx));
           }
           auto endIdx=*frontIdx.rbegin();
           if(height[i]>height[endIdx])
               frontIdx.push_back(height[i]);
       }
       return ret;
   }
};
*/

//for(int i=0;i<n;++i)
//    for(int j=i+1;j<n;++j)
//        ...

class Solution
{
public :
    int maxArea( vector < int >& height)
    {
        int si = height . size();
        int low = 0 , high = si - 1;
        int ret = 0;
        while( low < high)
        {
            ret = max( ret , min( height [ low ], height [ high ]) *( high - low));
            if( height [ low ] < height [ high ])
                ++ low;
            else
                -- high;
        }
        return ret;
    }
};

int main()
{
    Solution solution;
    auto n = 0;
    while( cin >>n)
    {
        vector < int > ve;
        for( int i = 0; i <n; ++ i)
        {
            int tmp;
            cin >> tmp;
            ve . push_back( tmp);
        }
        cout << solution . maxArea( ve) << endl;
    }
    return 0;
}
目录
相关文章
|
11月前
|
人工智能 容器
Leetcode 11. Container With Most Water
题目可以这么理解,在i位置有条高为ai的竖线,让你选出两台竖线构成一个容器,使得该容器装的水最多,注意容器不能倾斜。
43 3
|
11月前
Leetcode 365. Water and Jug Problem
一句话理解题意:有容积为x和y升的俩水壶,能不能量出z升的水。 我刚开始看到这题,立马就想了下暴力搜索的可能性,但考虑了下数据大小,立马放弃这个暴力的想法,于是意识到肯定有比较简单的数学方法,其实我自己没想到,后来看还是看了别人的代码,很多博客都直接给出了解法, 但没介绍为什么能这么解。所以我决定解释下我自己的思路。
43 0
LeetCode 417. Pacific Atlantic Water Flow
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。 规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。 请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。
103 0
LeetCode 417. Pacific Atlantic Water Flow
LeetCode 407. Trapping Rain Water II
我们把最外面的四边当成四面墙,想象海水面不断的升高,首先会浸过墙面最低的格子,如果墙面最低格子的四周(出了在墙面的格子)有比它矮的格子,那么这就可以形成一个蓄水池,蓄水池的最高高度就是墙面最低的格子,于是我们计算这个蓄水池可以获得的蓄水量;然后这个蓄水池被添加到墙面中;继续在墙面中找最低的格子;
90 0
LeetCode 407. Trapping Rain Water II
|
索引
LeetCode 42 Trapping Rain Water
给定n个非负整数,每个非负整数表示一个宽度为1的柱子,计算下雨后能够捕获多少水.
61 0
LeetCode 42 Trapping Rain Water
|
机器学习/深度学习 PHP 索引
[Leetcode 之 PHP 解析 (42. Trapping Rain Water)
[Leetcode 之 PHP 解析 (42. Trapping Rain Water)
103 0
[Leetcode 之 PHP 解析 (42. Trapping Rain Water)
|
容器
Leetcode-Medium 11. Container With Most Water
Leetcode-Medium 11. Container With Most Water
92 0
Leetcode-Medium 11. Container With Most Water
|
数据库
LeetCode(数据库)- The Airport With the Most Traffic
LeetCode(数据库)- The Airport With the Most Traffic
124 0
LeetCode - 42. Trapping Rain Water
42. Trapping Rain Water  Problem's Link  ---------------------------------------------------------------------------- Mean:  在坐标上给你一些竖直放置的条形积木,问你这个积木能够容纳多少液体.
895 0