这是一个leet code出现的问题:
给 n 个非负整数 $a_1$，$a_2$，…，$a_n$，每个数代表坐标中的一个点(i, $a_i$) 。在坐标内画 n 条垂直线，垂直线 i的两个端点分别为(i, $a_i$) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：不能倾斜容器
更详细的描述请访问：https://leetcode-cn.com/problems/container-with-most-water/
首先可以想到的最简单的方法，就是暴力求解，将所有的面积都计算出来，取最大值即可。下面给出(Racket)[https://racket-lang.org/]的代码，得益于函数式语言和S表达式强大的表现力，代码可以很短：
(define/contract (max-area height) (-> (listof exact-integer?) exact-integer?)
(define len (length height))
(cond
((< len 2) 0)
((= len 2) (area (list 1 (car height)) (list 2 (cadr height))))
(else (max (each-area height) (max-area (cdr height))))))
(define (area n1 n2)
(* (- (car n2) (car n1)) (min (cadr n1) (cadr n2))))
(define (each-area height)
(let ([first (list 1 (car height))])
(foldl max 0 (map (lambda (i h) (area first (list i h))) (range 2 (add1 (length height)) ) (cdr height)))))
上述解法虽然正确，但是效率很低, 如果有10000个整数，即n=10000，其执行时间超过了2秒：
(time (max-area (build-list 10000 (lambda(x) (random 1000000)))))
=> cpu time: 2387 real time: 2466 gc time: 137
那么有更好的解决方法吗？
显然可以认为所有整数都保存在一个列表或者数组中，假设我们有两个指针，一个叫head，指向第一个整数, 表示为：head -> (i, $h_i$)，i为列表下标， $h_i$代表第i个整数值；另一个叫tail，指向最后一个整数，表示为tail -> (j, $h_j$)，我们可以仅仅利用这两个指针的移动，就能计算出最大的面积，其过程为：
- 计算由head和tail围成的矩形的面积$S_{ij}$, 矩形的长度x = j - i, 高度y = min ($h_i$, $h_j$);
- 将矩形收窄一格，即x减少1，那么有两种收窄方式：
- 将高度短的一侧收窄，那么，收窄后高度可能变大，则面积可能增大;
- 将高度长的一侧收窄，由于另一侧不变,但是长度变小了一格，则面积会变小;
- 因此，需要移动高度短的一侧，才有可能找到面积更大的矩形
很显然，使用双指针算法，时间复杂度降低到了$O(n)$。
Racket 版本
;;better solution
(define/contract (max-area-pair-pointer height) (-> (listof exact-integer?) exact-integer?)
(define (area n1 n2)
(* (- (car n2) (car n1)) (min (cadr n1) (cadr n2))))
(let ([len (length height)])
(if (< len 2) 0
(let loop ([h height] [hindex (range 0 len)]
[rheight (reverse height)] [rindex (reverse (range 0 len))]
[maxa 0])
(let* ([head (list (car hindex) (car h))] [tail (list (car rindex) (car rheight))] [a (area head tail)])
(if (= (car head) (car tail)) maxa
(if (> (cadr head) (cadr tail))
(loop h hindex (cdr rheight) (cdr rindex) (max maxa a))
(loop (cdr h) (cdr hindex) rheight rindex (max maxa a)))
))))))
如果使用这个方法计算10000个整数的面积，执行时间只需1毫秒，而且不需要GC（对照暴力破解版本，2+秒）
(time (max-area-pair-pointer (build-list 10000 (lambda(x) (random 1000000)))))
=> cpu time: 1 real time: 1 gc time: 0
Rust版本
同时提供一个Rust版本的实现，
use std::cmp::{max, min};
type HeightType = i64;
#[derive(Debug)]
struct Solution {}
impl Solution {
pub fn max_area(height: Vec<HeightType>) -> HeightType {
let len = height.len();
return if len < 2 {
0
} else {
let mut max_area = 0;
let mut hi = 0;
let mut ti = len - 1;
while ti > hi {
let hd = height.get(hi).unwrap();
let td = height.get(ti).unwrap();
let a = ((ti - hi) as HeightType) * min(hd, td);
max_area = max(max_area, a);
if hd < td {
hi += 1;
} else {
ti -= 1;
}
}
max_area
};
}
}
两个版本做一个简单的比较：
| size | Racket(8.0 CS) | Rust(1.50.0) |
|---|---|---|
| 100000 | 49ms | 60ms |
| 1000000 | 560ms | 550ms |
| 10000000 | 5s | 5.6s |
两个版本的实现均未使用编译器优化,令人意外的是Racket的执行效率与Rust几乎没有差别，使用了CS编译器的Racket真是突飞猛进。 由于我的Rust经验并不是很多，或许有更好的写法。从测试可以看到Racket至少在CPU密集型应用中可堪大用。
