Largest Rectangle in Histogram LeetCode solution in Rust

1
impl Solution {
2
  pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
3
    let mut hs = heights.clone();
4
    hs.push(0);
5
    hs.insert(0, 0);
6

7
    fn bounds(hs: &Vec<i32>) -> Vec<usize> {
8
      let mut left = vec![0; hs.len()];
9
      for i in 1..hs.len() {
10
        left[i] = if hs[i] > hs[i - 1] {
11
          i - 1
12
        } else if hs[i] == hs[i - 1] {
13
          left[i - 1]
14
        } else {
15
          let mut j = left[i - 1];
16
          while j >= 0 && hs[j] >= hs[i] && j != left[j] {
17
            j = left[j];
18
          }
19
          j
20
        };
21
      }
22
      left
23
    }
24
    let rs: Vec<i32> = hs.clone().into_iter().rev().collect();
25
    let bounds_l = bounds(&hs);
26
    let bounds_r: Vec<usize> = bounds(&rs)
27
      .into_iter()
28
      .rev()
29
      .map(|i| hs.len() - 1 - i)
30
      .collect();
31
    bounds_l
32
      .iter()
33
      .zip(bounds_r.iter())
34
      .enumerate()
35
      .map(|(i, (l, r))| (r - l - 1) * hs[i] as usize)
36
      .max()
37
      .unwrap() as i32
38
  }
39
}