2022-09-25：给定一个二维数组 matrix，数组中的每个元素代表一棵树的高度。 你可以选定连续的若干行组成防风带，防风带每一列的防风高度为这一列的最大值 防风带整体的防风高度为，所有列防风高度

use rand::Rng;use std::iter::repeat;fn main() {    let n_max = 10;    let m_max = 10;    let v_max = 50;    let test_time = 1000;    println!("测试开始");    for _ in 0..test_time {        let n = rand::thread_rng().gen_range(0, n_max) + 1;        let m = rand::thread_rng().gen_range(0, m_max) + 1;        let mut matrix = generate_matrix(n, m, v_max);        let k = rand::thread_rng().gen_range(0, n) + 1;        let ans1 = best_height1(&mut matrix, k);        let ans2 = best_height2(&mut matrix, k);        if ans1 != ans2 {            println!("出错了");            break;        }    }    println!("测试结束");}
const MAX_VALUE: i32 = 1 << 31 - 1;
fn best_height1(matrix: &mut Vec<Vec<i32>>, k: i32) -> i32 {    let n = matrix.len() as i32;    let m = matrix[0].len() as i32;    let mut ans = 0;    for start_row in 0..n {        let mut bottle_neck = MAX_VALUE;        for col in 0..m {            let mut height = 0;            let mut end_row = start_row;            while end_row < n && (end_row - start_row + 1 <= k) {                height = get_max(height, matrix[end_row as usize][col as usize]);                end_row += 1;            }            bottle_neck = get_min(bottle_neck, height);        }        ans = get_max(ans, bottle_neck);    }    return ans;}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}
fn best_height2(matrix: &mut Vec<Vec<i32>>, k: i32) -> i32 {    let n = matrix.len() as i32;    let m = matrix[0].len() as i32;    let mut window_maxs: Vec<Vec<i32>> = repeat(repeat(0).take(n as usize).collect())        .take(m as usize)        .collect();
    let mut window_l_r: Vec<Vec<i32>> = repeat(repeat(0).take(2).collect())        .take(m as usize)        .collect();    for i in 0..k {        add_row(matrix, m, i, &mut window_maxs, &mut window_l_r);    }    let mut ans = bottle_neck(matrix, m, &mut window_maxs, &mut window_l_r);    for i in k..n {        add_row(matrix, m, i, &mut window_maxs, &mut window_l_r);        delete_row(m, i - k, &mut window_maxs, &mut window_l_r);        ans = get_max(            ans,            bottle_neck(matrix, m, &mut window_maxs, &mut window_l_r),        );    }    return ans;}
fn add_row(    matrix: &mut Vec<Vec<i32>>,    m: i32,    row: i32,    window_maxs: &mut Vec<Vec<i32>>,    window_l_r: &mut Vec<Vec<i32>>,) {    for col in 0..m {        while window_l_r[col as usize][0] != window_l_r[col as usize][1]            && matrix                [window_maxs[col as usize][(window_l_r[col as usize][1] - 1) as usize] as usize]                [col as usize]                <= matrix[row as usize][col as usize]        {            window_l_r[col as usize][1] -= 1;        }        window_maxs[col as usize][window_l_r[col as usize][1] as usize] = row;        window_l_r[col as usize][1] += 1;    }}
fn delete_row(m: i32, row: i32, window_maxs: &mut Vec<Vec<i32>>, window_l_r: &mut Vec<Vec<i32>>) {    for col in 0..m {        if window_maxs[col as usize][window_l_r[col as usize][0] as usize] == row {            window_l_r[col as usize][0] += 1;        }    }}
fn bottle_neck(    matrix: &mut Vec<Vec<i32>>,    m: i32,    window_maxs: &mut Vec<Vec<i32>>,    window_l_r: &mut Vec<Vec<i32>>,) -> i32 {    let mut ans = MAX_VALUE;    for col in 0..m {        ans = get_min(            ans,            matrix[window_maxs[col as usize][window_l_r[col as usize][0] as usize] as usize]                [col as usize],        );    }    return ans;}
fn generate_matrix(n: i32, m: i32, v: i32) -> Vec<Vec<i32>> {    let mut matrix: Vec<Vec<i32>> = repeat(repeat(0 as i32).take(m as usize).collect())        .take(n as usize)        .collect();    for i in 0..n {        for j in 0..m {            matrix[i as usize][j as usize] = rand::thread_rng().gen_range(0, v) + 1;        }    }    return matrix;}