Java 导弹拦截系统最小配备数量算法解析

某国为了防御敌国的导弹袭击，开发出了一种导弹拦截系统。该系统存在一个缺陷：虽然第一发炮弹能够到达任意高度，但之后每一发炮弹的高度不能高于前一发。

假设雷达已捕捉到敌国导弹来袭，且该拦截系统尚在试用阶段，可能无法拦截所有导弹。现给定导弹依次飞来的高度（雷达给出的高度不大于 30000 的正整数），需要计算拦截所有导弹所需的最少导弹拦截系统数量。

输入：

n 颗导弹依次飞来的高度（1 <= n <= 1000）

输出：

拦截所有导弹所需的最少系统数 k

算法思路：

首先，考虑最简单的情况，即只有一颗导弹来袭，此时需要配备一套拦截系统。

然后考虑两颗导弹的情况：

如果第二颗导弹的高度小于第一颗导弹，则需要再配备一套拦截系统。
否则，只需要一套拦截系统即可。

对于第三颗导弹，有三种情况：

高度小于第二颗导弹，需要再配备一套拦截系统。
高度大于等于第二颗导弹，但小于第一颗导弹，也需要再配备一套拦截系统。
高度大于等于第一颗导弹，则只需要两套拦截系统即可。

以此类推，可以得到一个贪心思路：

对于每颗导弹，如果它的高度小于之前所有导弹的高度，则需要再配备一套拦截系统；否则只需要更新之前最高的导弹高度即可。

最后，需要注意的是，最后一套拦截系统的数量需要加 1。

代码实现：

import java.util.Scanner;

public class MissileIntercept {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 导弹数量
        int[] heights = new int[n]; // 导弹高度数组
        for (int i = 0; i < n; i++) {
            heights[i] = scanner.nextInt();
        }

        int k = 1; // 最少系统数量
        int maxHeight = heights[0]; // 当前最高高度
        for (int i = 1; i < n; i++) {
            if (heights[i] < maxHeight) { // 如果当前高度小于最高高度，则需要新系统
                k++;
                maxHeight = heights[i]; // 更新最高高度
            } else if (heights[i] > maxHeight) { // 如果当前高度大于最高高度，则更新最高高度
                maxHeight = heights[i];
            }
        }

        System.out.println(k); // 输出最少系统数量
    }
}

示例：

输入： 5 30 20 40 10 35

输出： 3

解释：

第一个系统拦截高度为 30 的导弹。
第二个系统拦截高度为 20 和 10 的导弹。
第三个系统拦截高度为 40 和 35 的导弹。

因此，最少需要配备 3 个拦截系统。