competitive_library/algorithm/
largest_rectangle.rs

1//! 最大長方形
2
3use std::collections::VecDeque;
4
5pub fn largest_rectangle(arg: &[i64]) -> i64 {
6    let mut histogram = arg.to_vec();
7    histogram.push(0);
8
9    let mut stack = VecDeque::new();
10    let mut ans = 0;
11
12    for (right, &h) in histogram.iter().enumerate() {
13        if let Some(&(_, value)) = stack.back()
14            && value <= h
15        {
16            stack.push_back((right as i64, h));
17            continue;
18        }
19        let mut most_left = right as i64;
20        while !stack.is_empty() && stack[stack.len() - 1].1 > h {
21            let (left, value) = stack.pop_back().unwrap();
22            most_left = left;
23            ans = ans.max(value * (right as i64 - most_left));
24        }
25        stack.push_back((most_left, h));
26    }
27
28    ans
29}
30
31#[cfg(test)]
32mod tests {
33    use super::*;
34    #[test]
35    fn test_largest_rectangle() {
36        assert_eq!(largest_rectangle(&[0, 2, 5, 6, 4, 2, 3, 1]), 12);
37        assert_eq!(largest_rectangle(&[2, 4, 4, 9, 4, 9]), 20);
38        assert_eq!(largest_rectangle(&[200, 4, 4, 9, 4, 9]), 200);
39    }
40}