10.12ContainerWithMostWater - WisperDin/blog GitHub Wiki

desc

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 and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

 

Example:

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

思路

根据公式 area = min(h(t2),h(t1)) * (t2-t1)

以下简化为 area = min * dist

t 为数组的索引， h(t) 为对应索引处的值

• 暴力 O(N^2) 枚举所有可能，计算最大的area
• 排除法， O(N) 通过式子的特性，尽可能的排除不需要计算的对象 leetcode上解释

leetcode上面已经说的很详细了，对

[1,8,6,2,5,4,8,3,7]
 0 1 2 3 4 5 6 7 8
 
从左右两边向中间收缩，寻找最大值
1. h(0)<h(8) 此是 area = 1 * (8-0)  此时min = 1 , dist = 8 
!! 对于 0 位置来说，可以排除的结果对 0-1 0-2 0-3 ... 0-7
为什么呢? 因为 0-1 ... 0-7 其中 min <= 1 且 dist < 8 
所以这些结果对的值永远不会大于 0 - 8

根据这种方法收缩，可以在排除很多结果对的情况下，在O(N)情况下找到最大的area

实现

func maxArea(height []int) int {
    if len(height)<2{
        return -1
    }
    
    l := 0
    r := len(height)-1 
    area := 0
    for l<r {
        tmpMax := 0
        if height[l]<height[r] {
            tmpMax = height[l] * (r-l)
            l++
        }else {
            tmpMax = height[r] * (r-l)
            r--
        }
        if tmpMax > area {
            area = tmpMax
        }
    }
    return area
}

总结

对于公式，可以制造条件将其中某个变量控制到从某个特殊值开始，再在这个条件下单独研究另一个变量

在这个题目下，制造了从两端开始收缩的环境，使得 dist 变量 从最大开始，则对于两端内的其他结果对，其 dist 必定更小，再研究min变量，对于当前结果对的最小元素 (设为M) 来所，这个元素与两端内 的任意元素组成一对，其min<=M

结论: 排除当前两端内,与当前最小元素组成的结果对(实现来说，就直接跳过该最小元素，继续收缩)

(这些结果对被排除的原因):

• dist 更小
• min <= M