LIS 算法解決「出操隊形」問題：Java 實現最長山脈子序列

問題描述（經典 OJ 題：合唱隊形 / 出操隊形）

給定 n 位學生的身高序列 h[0..n-1]，需移除最少學生，使剩餘序列呈現 **先嚴格遞增後嚴格遞減** 的「山脈」形態（允許只遞增或只遞減，即山峰在兩端）。求最少移除人數。

等價於：求最長「先升後降」子序列長度 L，答案 = n - L。

算法思路：雙向 LIS + 合併

1. 正向遍歷，計算 inc[i] = 以 h[i] 結尾的 **最長遞增子序列長度**（標準 LIS O(n log n)）。
2. 反向遍歷，計算 dec[i] = 以 h[i] 開頭的 **最長遞減子序列長度**（等價於反序列的 LIS）。
3. 對每個 i 作為山峰，山脈長度 = inc[i] + dec[i] - 1（峰值重複計算一次）。
4. 取最大值 maxLen，結果 = n - maxLen。

核心代碼實現

public class MountainFormation {
    /** O(n log n) LIS：返回每個位置結尾的 LIS 長度 */
    public static int[] lisLengths(int[] a) {
        int n = a.length;
        int[] dp = new int[n];      // dp[len] = 最小結尾值
        int[] len = new int[n];     // 結果：每個位置的 LIS 長度
        int size = 0;
        for (int i = 0; i < n; i++) {
            int x = a[i];
            int l = 0, r = size;
            while (l < r) {
                int m = (l + r) >>> 1;
                if (dp[m] < x) l = m + 1;
                else r = m;
            }
            dp[l] = x;
            len[i] = l + 1;
            if (l == size) size++;
        }
        return len;
    }

    public static int minRemovals(int[] heights) {
        int n = heights.length;
        if (n <= 2) return 0; // 0/1/2 個人天然滿足

        // 1. 正向 LIS
        int[] inc = lisLengths(heights);

        // 2. 反向 LIS（等價於遞減）
        int[] rev = new int[n];
        for (int i = 0; i < n; i++) rev[i] = heights[n - 1 - i];
        int[] decRev = lisLengths(rev);
        int[] dec = new int[n];
        for (int i = 0; i < n; i++) dec[i] = decRev[n - 1 - i];

        // 3. 合併求最大山脈長度
        int maxMountain = 0;
        for (int i = 0; i < n; i++) {
            // 必須同時有左升右降（或允許單邊），這裡要求雙邊長度>1 才算真山峰
            // 若允許單邊，去掉 inc[i]>1 && dec[i]>1 判斷
            if (inc[i] > 1 && dec[i] > 1) {
                maxMountain = Math.max(maxMountain, inc[i] + dec[i] - 1);
            }
        }
        // 退化情況：全遞增或全遞減
        if (maxMountain == 0) {
            maxMountain = Math.max(Arrays.stream(inc).max().getAsInt(),
                                   Arrays.stream(dec).max().getAsInt());
        }
        return n - maxMountain;
    }

    // 測試
    public static void main(String[] args) {
        int[] h1 = {100, 154, 167, 159, 132, 105}; // 山峰 167
        System.out.println(minRemovals(h1)); // 0（已經是山脈）

        int[] h2 = {152, 152, 152, 152, 152}; // 全相等
        System.out.println(minRemovals(h2)); // 4（只能留 1 人）

        int[] h3 = {1, 2, 3, 4, 5}; // 全遞增
        System.out.println(minRemovals(h3)); // 0（允許只遞增）
    }
}

複雜度分析

• 時間：O(n log n)（兩次 LIS + 線性合併），滿足 n ≤ 1,000,000。
• 空間：O(n)（三個輔助數組）。

常見變體與避坑

總結

「出操隊形」本質是 **最長山脈子序列** 問題，通過 **正反向 LIS** 优雅轉化。掌握 O(n log n) LIS 模板與雙向合併技巧，可秒殺同類「先升後降」「先降後升」「雙峰」等變體題目。