2022-09-25：给定一个二维数组matrix，数组中的每个元素代表一棵树的高度。你可以选定连续

moonfdd 的个人博客 / 2 / 0 / 创建于 1年前

2022-09-25：给定一个二维数组matrix，数组中的每个元素代表一棵树的高度。
你可以选定连续的若干行组成防风带，防风带每一列的防风高度为这一列的最大值
防风带整体的防风高度为，所有列防风高度的最小值。
比如，假设选定如下三行
1 5 4
7 2 6
2 3 4
1、7、2的列，防风高度为7
5、2、3的列，防风高度为5
4、6、4的列，防风高度为6
防风带整体的防风高度为5，是7、5、6中的最小值
给定一个正数k，k <= matrix的行数，表示可以取连续的k行，这k行一起防风。
求防风带整体的防风高度最大值。

答案2022-09-25：

窗口内最大值和最小值问题。

代码用rust编写。代码如下：

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;
}