leetcode-go/medium/11.go

package main

import (
	"fmt"
)

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// 穷举
func maxAreaOld(height []int) int {
	n := len(height)
	max := 0
	for left := 0; left < n-1; left++ {
		for right := 1; right < n; right++ {
			tmp := (right - left) * minInt(height[left], height[right])
			if tmp > max {
				max = tmp
			}
		}
	}
	return max
}

// DP?
func maxArea(height []int) int {
	n := len(height)
	l, r := 0, n-1
	max := 0
	for l < r {
		hl, hr := height[l], height[r]
		tmp := (r - l) * minInt(hl, hr)
		if tmp > max {
			max = tmp
		}
		if hl < hr {
			for ; l < r && height[l] <= hl; l++ {
			}
		} else {
			for ; l < r && height[r] <= hr; r-- {
			}
		}
	}
	return max
}

func main() {
	arr := []int{1, 2, 4, 54, 6, 54}
	fmt.Println(maxArea(arr))
}