leetcode_rust/
container_with_most_water.rs

1#![allow(dead_code)]
2
3// equation: V_max(i,j) = max{V_max(i', j-1), V(i, j)} which i <= i' < j
4// V_max(i,j) means the max area from i to j.
5// bad O(n^2)!
6pub fn max_area(height: Vec<i32>) -> i32 {
7    type StartAndArea = (i32, i32);
8    // key: end; value: start, max_area
9    let mut dp: Vec<StartAndArea> = Vec::with_capacity(height.len());
10    dp.push((0, 0));
11    for j in 1..height.len() {
12        let mut max_area = 0;
13        let mut start = 0;
14        for i in 0..j {
15            let area = (j - i) as i32 * i32::min(height[i], height[j]);
16            if area > max_area {
17                start = i;
18                max_area = area;
19            }
20        }
21        max_area = i32::max(max_area, dp[j - 1].1);
22        dp.push((start as i32, max_area));
23    }
24    dp[dp.len() - 1].1
25}
26
27// O(n): Double pointers
28pub fn max_area2(height: Vec<i32>) -> i32 {
29    let mut max_area = 0;
30    let mut left = 0;
31    let mut right = height.len() - 1;
32    while left < right {
33        let area = (right - left) as i32 * i32::min(height[left], height[right]);
34        max_area = i32::max(max_area, area);
35        if height[left] < height[right] {
36            left += 1;
37        } else {
38            right -= 1;
39        }
40    }
41
42    max_area
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn test1() {
51        assert_eq!(max_area(vec![1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
52        assert_eq!(max_area(vec![1, 2]), 1);
53    }
54
55    #[test]
56    fn test2() {
57        assert_eq!(max_area2(vec![1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
58        assert_eq!(max_area2(vec![1, 2]), 1);
59    }
60}
leetcode_rust/container_with_most_water.rs

leetcode_rust/
container_with_most_water.rs
