Container With Most Water

Description

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.

给出n个点，它们与X轴有n条垂线，每两条垂线与X轴形成的U型容器，找出最大“容积”(面积）

Solution

从两边往中间逼近。每次循环收紧矮的一边。

 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
27
28
29
30
31
32

func maxArea(height []int) int {
    area := 0
    left, right := 0, len(height)-1

    for left < right {
        width := right - left
        h := 0

        if height[right] > height[left] {
            h = height[left]
            left++
        } else {
            h = height[right]
            right--
        }

        a := width * h
        if a > area {
            area = a
        }
    }

    return area
}

func min(a, b int) int {
    if a > b {
        return b
    }

    return a
}

Similar Problem

42. Trapping Rain Water