给定一个二维数组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行一起防风。
求防风带整体的防风高度最大值。
窗口内最大值和最小值问题。
代码用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;
}执行结果如下：
