largest_rectangle_area.rs

impl Solution {
    fn recurse(heights: &[i32]) -> i32 {
        if heights.len() == 0 {
            return 0
        }
        if heights.len() == 1 {
            return heights[0]
        }

        let min = heights.iter().min().cloned().unwrap_or_default();
        let size = min * (heights.len() as i32);

        let partition = heights.iter().position(|&i|i==min).unwrap_or_default();
        let partition_right = heights[partition..].iter().position(|&i|i>min).unwrap_or(heights.len()-1-partition) + partition;

        return size.max(
            Self::recurse(&heights[0..partition])
        ).max(
            Self::recurse(&heights[partition_right..])
        )
    }

    pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
        return Self::recurse(&heights);
    }
}