盛最多水的容器

盛最多水的容器

Posted by LY on March 1, 2019

在这里小小推荐下我的个人博客

csdn:雷园的csdn博客

个人博客:雷园的个人博客

简书:雷园的简书

前言

  1. 最近准备把算法慢慢的捡起来,所以准备日更一道算法题目,难度自然是由简入难,所以同学们可以每天都来看看小编的更新。
  2. 北京的生活总是匆忙的,希望在北京的活着将要来北京生活的伙伴们,不要被这无情的生活淹没。最起码抽出一些时间,来做一些自己喜欢的事情。

题目:

给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

image-20190301144704764

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解题思路

  1. 如题意,垂直的两条线段将会与坐标轴构成一个矩形区域,较短线段的长度将会作为矩形区域的宽度,两线间距将会作为矩形区域的长度,而我们必须最大化该矩形区域的面积。
  2. 这种方法背后的思路在于,两线段之间形成的区域总是会受到其中较短那条长度的限制。此外,两线段距离越远,得到的面积就越大。
  3. 我们可以通过前后双标,或者使用前后双指针来解决这到问题。
  4. 当然也可以使用暴力的解题方法,但是时间复杂度会比较高,所以我们这里使用双标的方法来解决。
  5. 我们在由线段长度构成的数组中使用两个指针,一个放在开始,一个置于末尾。 此外,我们会使用变量 maxArea 来持续存储到目前为止所获得的最大面积。 在每一步中,我们会找出指针所指向的两条线段形成的区域,更新 maxArea,并将指向较短线段的指针向较长线段那端移动一步。
  6. 现在,为了使面积最大化,我们需要考虑更长的两条线段之间的区域。如果我们试图将指向较长线段的指针向内侧移动,矩形区域的面积将受限于较短的线段而不会获得任何增加。但是,在同样的条件下,移动指向较短线段的指针尽管造成了矩形宽度的减小,但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段,这可以克服由宽度减小而引起的面积减小。

解题代码

	public static void main(String[] args) {
        int[] a = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea(a));
    }
    public static int maxArea(int[] height) {
        int start = 0; // 定义头标
        int end = height.length - 1; // 定位尾标
        int maxArea = 0; // 定义最大面积
        while (start < end) {
             // 定义宽度等于两者中较小的
            int kuan = height[start] > height[end] ? height[end] : height[start];
            // 比较面积大小并替换
            maxArea = maxArea > kuan * (end - start) ? maxArea : kuan * (end - start); 
            // 判断首位标处值的大小并执行操作
            if (height[start] > height[end]) {
                end--;
            } else start++;
        }
        return maxArea;
    }

最后说两句

  1. 所有的题目都有很多种解法,我的一定不是最好的,甚至可以说是比较低端的解法,希望大牛们多多指教!!!
  2. 如果朋友们对算法、编程有很大兴趣的话,可以私信我,大家一同探讨;相互学习、共同进步。
  3. 朋友们如果对这道题目有更好的解法,希望可以在评论中指出,让大家一起讨论学习。
  4. 最后感谢大家的阅读以及关注,谢谢大家!!!