11. Container With Most Water

news/2024/7/7 1:38:35 标签: java, c#, python

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

说明：你不能倾斜容器，且 n 的值至少为 2

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

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

说实话，没这图我还真没看明白这题啥意思，然而英文站点的图居然挂了= =
抱着尝试的心态输入了-ch，果然路由是镜像的。

至于题目嘛。。不管不管Brute Force：

 1 public class Solution {
 2     public int MaxArea(int[] height) {
 3         int result = 0;
 4         for (int i = 0; i < height.Length - 1; i ++)
 5         {
 6             for (int j = i + 1; j < height.Length; j ++)
 7             {
 8                 result = Math.Max(Math.Min(height[i], height[j]) * (j - i), result);
 9             }
10         }
11         return result;
12     }
13 }

O(n2)的复杂度竟然让运行时间达到了1000+。。

优化

可以说大部分算法优化的思路就是省去不必要的计算，那这道题有哪些不必要的计算呢？

因为题目规定水的高度是由较短的一条线决定的，那么对于数组中的最小值，能和他组成最大面积的那条线即是距离他最远的值。

那么依次类推，我们需要考虑比较的，仅仅是“每条线和比自身长的且距离最远的线组成的面积”。

以[1,8,6,2,5,4,8,3,7]为例：

考虑的情况有：

f(1,7) = 1*8

f(8,8) = 8*5

f(6,7) = 6*7

f(2,7) = 2*5

f(5,7) = 5*4

f(4,7) = 4*3

f(8,8) = 8*5

f(3,8) = 3*6

f(7,8) = 7*7

那么显然，这道题只需要O(n)的复杂度就可以解决了。

但是这种思路在实际编程时不太好实现，毕竟需要依次比较大小。

双指针

兜了半天圈子其实这道题也算是个标准的双指针题，从两边开始，不断向中间移动较小的那一边的值。

这里还有个可以优化的点，就是如果移动后指针所在的值没有大于之前所在的值，那也不必计算了。

 1 public class Solution {
 2     public int MaxArea(int[] height) {
 3         int l = 0;
 4         int r = height.Length - 1;
 5         int temp = Math.Min(height[l], height[r]);
 6         int result = temp * (r - l);
 7         while (l < r)
 8         {
 9             if (height[l] < height[r])
10             {
11                 l ++;
12                 if (height[l] <= temp)
13                 {
14                     continue;
15                 }
16             }
17             else
18             {
19                 r --;
20                 if (height[r] <= temp)
21                 {
22                     continue;
23                 }
24             }
25             temp = Math.Min(height[l], height[r]);
26             result = Math.Max(temp * (r - l), result);
27         }
28         return result;
29     }
30 }