LeetCode11盛最多水的容器

发表于 | 更新于 | 分类于 |

题目说明：

给定 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。

示例:

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

题目思路：

第一眼看到这题的时候，就想这题一定会有快速做出来的方法的，如果暴力来做很可能会超时，然后想了一会，没找到方法。就用暴力法写了，逐个遍历比较，时间复杂度达到了 $O(n^2)$ ，空间的复杂度是 $O(1)$ 的，使用的空间是固定的。

一开始的暴力写法是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
max = 0
      temp_y = 0
      for i in range(len(height)-1):
          if height[i] <= temp_y:
              continue
          else:
              temp_y = height[i]
          for j in range(i+1, len(height)):
              x = j - i
              y = height[i]
              if height[j] < height[i]:
                  y = height[j]
              temp = x * y
              if temp > max:
                  max = temp
      return max

提交之后就超时了…

然后就想了另外一个方法，想的是，先把木板（数字）进行排序，然后从低往高遍历，因为是从低向高遍历的，所以就不需要考虑高度的问题，只需要考虑宽度的问题即可，用当前木板的的原索引值与比其高的木板的原索引值的绝对值作为宽度。本以为这样做起来挺好的，时间复杂度也不会很高。但是，忽略了取

min()``` 值的问题，再Python中，这两个操作的时间复杂度是$O(n)$的，所以再加上之前的遍历操作，最后的时间复杂度还是$O(n^2)$的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这次的解答如下：

```python
		a = sorted(height)
        index_arra = []
        for item in a:
            temp = height.index(item)
            index_arra.append(temp)
            height[temp] = -1

        result = 0
        for index, item in enumerate(a):
       	    if index <= len(a)-2:
                min_index = min(index_arra[index + 1:])
                max_index = max(index_arra[index + 1:])

                temp = abs(index_arra[index] - min_index)
                if abs(index_arra[index] - max_index) > temp:
                    temp = abs(index_arra[index] - max_index)

                current_result = temp * item
                if current_result > result:
                    result = current_result

        return result

正确解答

最后，看了提示，说用双指针法，两个指针从头尾分别向中间遍历即可。

用这个方法，关键是需要明白，指针移动时，是短板的指针向长板的指针移动，直到短板的指针找到下一个长板为止，如果在找到长板的途中遇到的都比之前的短板低，则可直接跳过。

我下面的解答，没有处理短板在寻找下一个长板的过程中，遇到更小的短板的问题（加一个判断，就不需要计算面积了，更节省时间）。不过因为时间复杂度本身就已经降低到$O(n)$了，所以也就通过了。

GitHub地址：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c11.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
result = 0
      start = 0
      end = len(height)-1

      while start < end:
          x = end - start
          y = min(height[start], height[end])
          result = max(result, x * y)
          if height[start] > height[end]:
              end = end - 1
          else:
              start = start + 1

      return result