2022-07-05：给定一个数组，想随时查询任何范围上的最大值。 如果只是根据初始数组建立、并且以后没有修改， 那么RMQ方法比线段树方法好实现，时间复杂度O(N*logN)，额外空间复杂度O(N*

2022-07-05：给定一个数组，想随时查询任何范围上的最大值。
如果只是根据初始数组建立、并且以后没有修改，
那么RMQ方法比线段树方法好实现，时间复杂度O(NlogN)，额外空间复杂度O(NlogN)。
来自小红书。3.13笔试。

答案2022-07-05：

RMQ范围最大值和最小值查询，不支持更新。
空间复杂度：O(N*logN)。
查询复杂度：O(1)。

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

use rand::Rng;

fn main() {

    let nn: i32 = 150;

    let vv = 200;

    let test_time_out = 20000;

    let test_time_in = 200;

    println!("测试开始");

    for i in 0..test_time_out {

        let n = rand::thread_rng().gen_range(0, nn) + 1;

        let mut arr = random_array(n, vv);

        let mut arr2=arr.clone();

        let m = arr.len() as i32;

        let mut rmq = RMQ::new(&mut arr);

        let mut right = Right::new(&mut arr2);

        for _ in 0..test_time_in {

            let a = rand::thread_rng().gen_range(0, m) + 1;

            let b = rand::thread_rng().gen_range(0, m) + 1;

            let l = get_min(a, b);

            let r = get_max(a, b);

            let ans1 = rmq.max(l, r);

            let ans2 = right.max(l, r);

            if ans1 != ans2 {

                println!("出错了!{}", i);

                println!("ans1 = {}", ans1);

                println!("ans2 = {}", ans2);

                break;

            }

        }

    }

    println!("测试结束");

}

pub struct RMQ {

    pub max: Vec<Vec<i32>>,

}

impl RMQ {

    // 下标一定要从1开始，没有道理！就是约定俗成！

    pub fn new(arr: &mut Vec<i32>) -> Self {

        // 长度！

        let n = arr.len() as i32;

        let mut ans: RMQ = RMQ { max: vec![] };

        // 2的几次方，可以拿下n

        let k = ans.power2(n);

        // n*logn

        let mut max: Vec<Vec<i32>> = vec![];

        for i in 0..n + 1 {

            max.push(vec![]);

            for _ in 0..k + 1 {

                max[i as usize].push(0);

            }

        }

        for i in 1..=n {

            // i 0：从下标i开始，往下连续的2的0次方个数，中，最大值

            // 1...1个

            // 2...1个

            // 3...1个

            max[i as usize][0] = arr[(i - 1) as usize];

        }

        ans.max = max;

        let mut j = 1;

        while (1 << j) <= n {

            // i...连续的、2的1次方个数，这个范围，最大值

            // i...连续的、2的2次方个数，这个范围，最大值

            // i...连续的、2的3次方个数，这个范围，最大值

            let mut i = 1;

            while i + (1 << j) - 1 <= n {

                // max[10][3]

                // 下标10开始，连续的8个数，最大值是多少

                // 1) max[10][2]

                // 2) max[14][2]

                ans.max[i as usize][j as usize] = get_max(

                    ans.max[i as usize][(j - 1) as usize],

                    ans.max[(i + (1 << (j - 1))) as usize][(j - 1) as usize],

                );

                i += 1;

            }

            j += 1;

        }

        return ans;

    }

    pub fn max(&mut self, l: i32, r: i32) -> i32 {

        // l...r -> r - l + 1 -> 2的哪个次方最接近它！

        let k = self.power2(r - l + 1);

        return get_max(

            self.max[l as usize][k as usize],

            self.max[(r - (1 << k) + 1) as usize][k as usize],

        );

    }

    fn power2(&mut self, m: i32) -> i32 {

        let mut ans = 0;

        while (1 << ans) <= (m >> 1) {

            ans += 1;

        }

        return ans;

    }

}

// 为了测试

pub struct Right {

    pub max: Vec<Vec<i32>>,

}

impl Right {

    pub fn new(arr: &mut Vec<i32>) -> Self {

        let n = arr.len() as i32;

        let mut max: Vec<Vec<i32>> = vec![];

        for i in 0..n + 1 {

            max.push(vec![]);

            for _ in 0..n + 1 {

                max[i as usize].push(0);

            }

        }

        for l in 1..=n {

            max[l as usize][l as usize] = arr[(l - 1) as usize];

            for r in l + 1..=n {

                max[l as usize][r as usize] =

                    get_max(max[l as usize][(r - 1) as usize], arr[(r - 1) as usize]);

            }

        }

        Self { max }

    }

    pub fn max(&mut self, l: i32, r: i32) -> i32 {

        self.max[l as usize][r as usize]

    }

}

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 random_array(n: i32, v: i32) -> Vec<i32> {

    let mut arr: Vec<i32> = vec![];

    for _i in 0..n {

        arr.push(rand::thread_rng().gen_range(0, v));

    }

    return arr;

}

执行结果如下：

左神java代码

2022-07-05：给定一个数组，想随时查询任何范围上的最大值。 如果只是根据初始数组建立、并且以后没有修改， 那么RMQ方法比线段树方法好实现，时间复杂度O(N*logN)，额外空间复杂度O(N*的相关教程结束。