haar_lib/algo/
max_rect.rs

1//! 最大長方形
2use crate::chmax;
3use std::{
4    cmp::Ordering,
5    ops::{Mul, Range},
6};
7
8/// ヒストグラム中の最大面積長方形の面積を計算する。
9///
10/// **Time complexity** $O(|h|)$
11pub fn max_rect_in_histogram<T>(h: &[T]) -> (T, Range<usize>)
12where
13    T: From<usize> + Mul<Output = T> + Ord + Copy,
14{
15    let mut st: Vec<(T, usize)> = vec![];
16    let mut ret = T::from(0);
17    let mut lr = (0, 0);
18
19    for (i, &y1) in h.iter().enumerate() {
20        if let Some(&(y2, _)) = st.last() {
21            match y2.cmp(&y1) {
22                Ordering::Less => {
23                    st.push((y1, i));
24                }
25                Ordering::Greater => {
26                    let mut j = i;
27                    while let Some(&(y3, k)) = st.last() {
28                        if y3 <= y1 {
29                            break;
30                        }
31                        if chmax!(ret, y3 * T::from(i - k)) {
32                            lr = (k, i);
33                        }
34                        j = k;
35                        st.pop();
36                    }
37                    st.push((y1, j));
38                }
39                _ => {}
40            };
41        } else {
42            st.push((y1, i));
43        }
44    }
45
46    while let Some((y, i)) = st.pop() {
47        if chmax!(ret, y * T::from(h.len() - i)) {
48            lr = (i, h.len());
49        }
50    }
51
52    (
53        ret,
54        Range {
55            start: lr.0,
56            end: lr.1,
57        },
58    )
59}
60
61/// グリッド上の最大面積長方形の面積を計算する。
62///
63/// **Time complexity** $O(hw)$
64pub fn max_rect<T: Copy + PartialEq>(d: &[Vec<T>], value: T) -> usize {
65    let h = d.len();
66    let w = d[0].len();
67
68    let mut c = vec![vec![0; w]; h];
69    for i in 0..h {
70        for j in 0..w {
71            if d[i][j] == value {
72                c[i][j] = 1;
73            }
74        }
75    }
76
77    for i in 1..h {
78        for j in 0..w {
79            if c[i][j] == 1 {
80                c[i][j] += c[i - 1][j];
81            }
82        }
83    }
84
85    c.into_iter()
86        .map(|s| max_rect_in_histogram(&s).0)
87        .max()
88        .unwrap()
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94
95    #[test]
96    fn test_histogram() {
97        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_3_C
98
99        let a = [2, 1, 3, 5, 3, 4, 2, 1];
100        let (ans, Range { start: l, end: r }) = max_rect_in_histogram(&a);
101        assert_eq!(ans, 12);
102        assert_eq!(ans, a[l..r].iter().min().unwrap() * (r - l));
103
104        let a = [2, 0, 1];
105        let (ans, Range { start: l, end: r }) = max_rect_in_histogram(&a);
106        assert_eq!(ans, 2);
107        assert_eq!(ans, a[l..r].iter().min().unwrap() * (r - l));
108    }
109
110    #[test]
111    fn test_max_rect() {
112        // https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_3_B
113        assert_eq!(
114            max_rect(
115                &[
116                    vec![0, 0, 1, 0, 0],
117                    vec![1, 0, 0, 0, 0],
118                    vec![0, 0, 0, 1, 0],
119                    vec![0, 0, 0, 1, 0]
120                ],
121                0
122            ),
123            6
124        );
125    }
126}
haar_lib/algo/max_rect.rs

haar_lib/algo/
max_rect.rs
