2022-08-08: Given an array arr, it represents the height of the missiles that will appear in order from morning to night.When the cannon shoots missiles, once the cannon is set to shoot at a certain h

2022-08-08：给定一个数组arr,Indicates from morning to night,The heights of the missiles that will appear in turn.
When the cannon hits the missile,If once the cannon is set at a certain height to hit,Then the height of this cannon has to drop a little every time it hits.
(1) If only one cannon,Returns the maximum number of missiles that can be intercepted.
(2) If all missiles must be intercepted,Returns the minimum number of cannons.

答案2022-08-08：

问题一：最长递减子序列.There is just too much code on the web for the longest increasing subsequence,这里就不写了.
问题二：贪心+有序表.Hit it with the closest, slightly taller cannon that exists.

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

use std::collections::BTreeMap;
fn main() {
    
    let mut arr = vec![15, 7, 14, 6, 5, 13, 5, 10, 9];
    println!("ans = {}", num_of_cannon(&mut arr));
}

const MAX_VALUE: i32 = 1 << 31 - 1;

fn num_of_cannon(arr: &mut Vec<i32>) -> i32 {
    
    // key : The ending value of a certain cannon shot
    // value : How many cannons have the same ending value
    // 比如：
    // 一共有A、B、Cthree cannons
    // 如果AThe height of the cannon at this time is 17,BThe height of the cannon at this time is 7,CThe height of the cannon at this time is 13
    // then in the table：
    // 7, 1
    // 13, 1
    // 17, 1
    // 如果AThe height of the cannon at this time is 13,BThe height of the cannon at this time is 7,CThe height of the cannon at this time is 13
    // then in the table：
    // 7, 1
    // 13, 2
    let mut ends: BTreeMap<i32, i32> = BTreeMap::new();
    for num in arr.iter() {
    
        if ends.range(num + 1..).take(1).last() == None {
    
            ends.insert(MAX_VALUE, 1);
        }
        let ceil_key = *ends.range(num + 1..).take(1).last().unwrap().0;
        let ceil_value = *ends.range(num + 1..).take(1).last().unwrap().1;
        if ceil_value > 1 {
    
            ends.insert(ceil_key, ceil_value - 1);
        } else {
    
            ends.remove(&ceil_key);
        }
        ends.insert(
            *num,
            match ends.get(num) {
    
                Option::Some(v) => v + 1,
                Option::None => 1,
            },
        );
    }
    let mut ans = 0;
    for (_, value) in ends.iter() {
    
        ans += *value;
    }
    return ans;
}

执行结果如下：

左神java代码