• 热门专题

LeetCode11ContainerWithMostWater(最大水容器)

作者:  发布日期:2015-10-13 20:28:03
Tag标签:容器  
  • 翻译

    给定n个非负整数a1,a2,...,an,其中每个代表一个点坐标(i,ai)。
    
    n个垂直线段例如线段的两个端点在(i,ai)和(i,0)。
    
    找到两个线段,与x轴形成一个容器,使其包含最多的水。
    
    备注:你不必倾倒容器。

    翻译

    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.

    题目的意思是,数组中的每个数对应一条线段的长度,索引对应x坐标,两个索引可以组成一个底部的宽,高度就是前面所说的线段的长度,而既然是要盛水,高度就是两个线段中较短的一个。

    那么该怎么去解题呢?

    我水平不行,英文也不行,所以每次一开始都是用最简单的方法,旨在试试有没有理解题目的意思,即便超出时间/空间限制也没事。

    public int MaxAera(int[] height)
    {
        int area = 0;
        for (int i = 0; i < height.Length; i++)
        {
            for (int j = i + 1; j < height.Length; j++)
            {
                if (height[i] < height[j])
                    area = Math.Max(area, countArea(height, i, j));
            }
        }
        return area;
    }
    
    public int countArea(int[] height, int x, int y)
    {
        int h = height[x] > height[y] ? height[x] : height[y];
        int info = h * (y - x);
        return info;
    }

    很明显这样是不行的……

    那有那些部分可以简化呢?

    前面的方法是从数组左侧开始逐个向右遍历所有情况,但明显可以从两侧向中间进发,通过对应的max函数来保留最大的面积。

    当从左边进入到图中线段1位置,右边进入到线段5的时候。你不会想着右边继续进入线段6和7,因为你就是从那边过来的。

    那么是该左边的往右走,还是右边的往左走呢?

    如果是右边的往左走,虽然线段1变成了线段2,但是线段1到线段5的距离比线段2大,因此面积也大。所以走了之后面积反而小了。

    如果是右边的往左走,亲自行脑补:线段3和线段4是在同一位置,如果是到了线段4,那么容器的高度将从原本的线段5的长度变成线段1的长度,(虽然由于距离的变小,总面积仍可能变小,但请继续往下看),而如果到了线段3,虽然高度变小了,宽度变小了,但,那又何妨呢?因为你的maxArea还是在那里的,每次的计算后,当且仅当高度超过原本的高度之后才会覆盖原来的值。

    maxArea = Max(maxArea,newArea);

    也就是说,高度如果没有超过,就没有什么影响。

    这里写图片描述

    至于你说它会不会因为自增和自减而发生越界,如果

    int[] height = {10, 1, 2, 3, 4, 5, 6, 7, 11};

    假设这里的10和11对应线段1和线段6,请自行脑补:去掉线段7,既然线段1短于线段6,那么发生的是left++,而不是left–。所以,并不会越界的。反之,亦然。

    public class Solution
    {
        public int MaxArea(int[] height)
        {
            int left = 0, right = height.Length - 1;
            int maxArea = 0;
            while (left < right && left >= 0 && right <= height.Length - 1)
            {
                maxArea = Math.Max(maxArea, Math.Min(height[left], height[right]) * (right - left));
                if (height[left] > height[right])
                {
                    right--;
                }
                else
                {
                    left++;
                }
            }
            return maxArea;
        }
    }

    明天继续,加油!

    版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规