每日算法 — 使用java实现耐心排序：堆叠序列与最长递增子序列优化

引言

耐心排序（Patience Sorting）是一种优雅而高效的排序算法，其名称来源于单人纸牌游戏”Patience”的玩法规则。该算法不仅能完成排序，更是求解最长递增子序列（LIS）问题的最优解法之一。本文将使用Java实现耐心排序算法，深入讲解其原理、实现细节，以及如何利用该算法在O(n log n)时间内求解最长递增子序列问题。

核心算法思路

纸牌堆叠规则

想象你正在玩一个纸牌游戏，规则如下：
– 牌一张一张翻开
– 每张牌必须放到最左边一个牌顶大于等于它的牌堆上
– 如果没有这样的牌堆，就在最右边新建一个牌堆

最终，牌堆的数量就是最长递减子序列的长度；而通过贪心策略选择牌堆，则可得到最长递增子序列。

与LIS的关系

耐心排序与最长递增子序列之间存在深刻的数学联系：
– Dilworth定理：最少递减子序列划分数等于最长递增子序列长度
– 耐心排序的牌堆数 = 最长递增子序列长度
– 通过维护每个牌堆的顶牌，可在O(n log n)时间内完成

Java实现

基础耐心排序

import java.util.*;

/**
 * 耐心排序核心实现
 */
public class PatienceSorting {

    /**
     * 耐心排序主算法
     * @param arr 待排序数组
     * @return 排序后的数组
     */
    public static int[] sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr;
        }

        int n = arr.length;
        // piles[i] 存储第i个牌堆的顶牌（即该堆最小的元素）
        List<List<Integer>> piles = new ArrayList<>();

        // 第一阶段：分堆
        for (int num : arr) {
            placeCard(piles, num);
        }

        // 第二阶段：合并（类似K路归并）
        return mergePiles(piles, n);
    }

    /**
     * 将一张牌放到合适的牌堆
     * 使用二分查找找到最左边牌顶 >= num 的牌堆
     */
    private static void placeCard(List<List<Integer>> piles, int num) {
        int left = 0, right = piles.size();

        // 二分查找：找到第一个顶牌 >= num 的牌堆
        while (left < right) {
            int mid = left + (right - left) / 2;
            int topCard = piles.get(mid).get(piles.get(mid).size() - 1);
            if (topCard < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        if (left == piles.size()) {
            // 没有合适的牌堆，新建一个
            List<Integer> newPile = new ArrayList<>();
            newPile.add(num);
            piles.add(newPile);
        } else {
            // 放到找到的牌堆上
            piles.get(left).add(num);
        }
    }

    /**
     * K路归并所有牌堆
     */
    private static int[] mergePiles(List<List<Integer>> piles, int n) {
        int[] result = new int[n];
        int index = 0;

        // 使用优先队列进行K路归并
        // 每个元素: [值, 牌堆编号, 牌堆内位置]
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        // 初始化：每个牌堆的第一个元素
        for (int i = 0; i < piles.size(); i++) {
            if (!piles.get(i).isEmpty()) {
                pq.offer(new int[]{piles.get(i).get(0), i, 0});
            }
        }

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            result[index++] = curr[0];

            int pileIdx = curr[1];
            int cardIdx = curr[2];

            // 如果该牌堆还有下一个元素，加入优先队列
            if (cardIdx + 1 < piles.get(pileIdx).size()) {
                pq.offer(new int[]{piles.get(pileIdx).get(cardIdx + 1), pileIdx, cardIdx + 1});
            }
        }

        return result;
    }

    /**
     * 打印牌堆状态（用于调试）
     */
    public static void printPiles(List<List<Integer>> piles) {
        System.out.println("当前牌堆状态:");
        for (int i = 0; i < piles.size(); i++) {
            System.out.print("  堆" + i + ": ");
            for (int card : piles.get(i)) {
                System.out.print(card + " ");
            }
            System.out.println(" (顶牌=" + piles.get(i).get(piles.get(i).size() - 1) + ")");
        }
    }
}

最长递增子序列（LIS）求解

import java.util.*;

/**
 * 基于耐心排序的最长递增子序列求解器
 */
public class LISSolver {

    /**
     * 求解LIS长度（O(n log n)）
     */
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        // tails[i] 表示长度为i+1的递增子序列的最小末尾元素
        int[] tails = new int[nums.length];
        int size = 0;

        for (int num : nums) {
            // 二分查找：找到 tails 中第一个 >= num 的位置
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = num;
            if (left == size) {
                size++;
            }
        }

        return size;
    }

    /**
     * 求解LIS序列本身（O(n log n)）
     * @return 最长递增子序列
     */
    public static int[] findLIS(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];

        int n = nums.length;
        // tails[i] = 长度为i+1的递增子序列的最小末尾元素
        int[] tails = new int[n];
        // tailsIndex[i] = tails[i]对应的原数组下标
        int[] tailsIndex = new int[n];
        // prev[i] = 以i结尾的递增子序列的前驱元素下标
        int[] prev = new int[n];
        Arrays.fill(prev, -1);

        int size = 0;

        for (int i = 0; i < n; i++) {
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            tails[left] = nums[i];
            tailsIndex[left] = i;

            // 记录前驱
            if (left > 0) {
                prev[i] = tailsIndex[left - 1];
            }

            if (left == size) {
                size++;
            }
        }

        // 重建LIS序列
        int[] lis = new int[size];
        int k = tailsIndex[size - 1];
        for (int i = size - 1; i >= 0; i--) {
            lis[i] = nums[k];
            k = prev[k];
        }

        return lis;
    }

    /**
     * 求解最长递减子序列（LDS）
     */
    public static int[] findLDS(int[] nums) {
        // 对数组取反，转化为LIS问题
        int[] neg = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            neg[i] = -nums[i];
        }
        return findLIS(neg);
    }

    /**
     * 求解最长连续递增子序列
     */
    public static int[] findLCIS(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];

        int n = nums.length;
        int maxLen = 1, maxStart = 0;
        int currLen = 1, currStart = 0;

        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                currLen++;
            } else {
                if (currLen > maxLen) {
                    maxLen = currLen;
                    maxStart = currStart;
                }
                currLen = 1;
                currStart = i;
            }
        }

        if (currLen > maxLen) {
            maxLen = currLen;
            maxStart = currStart;
        }

        return Arrays.copyOfRange(nums, maxStart, maxStart + maxLen);
    }
}

扩展：耐心排序的完整可视化与K路归并优化

import java.util.*;

/**
 * 耐心排序的完整实现与扩展功能
 */
public class PatienceSortingExtended {

    /**
     * 带详细步骤追踪的耐心排序
     */
    public static SortResult sortWithTrace(int[] arr) {
        List<List<Integer>> piles = new ArrayList<>();
        List<String> steps = new ArrayList<>();

        for (int num : arr) {
            int pileIdx = findPile(piles, num);
            if (pileIdx == piles.size()) {
                piles.add(new ArrayList<>());
            }
            piles.get(pileIdx).add(num);
            steps.add(String.format("放置 %d 到堆%d", num, pileIdx));
        }

        int[] sorted = mergePilesOptimized(piles);
        return new SortResult(sorted, piles, steps);
    }

    /**
     * 优化的K路归并（使用败者树思想）
     */
    private static int[] mergePilesOptimized(List<List<Integer>> piles) {
        int total = 0;
        for (List<Integer> pile : piles) total += pile.size();

        int[] result = new int[total];
        int idx = 0;

        // 每个牌堆当前读取位置
        int[] positions = new int[piles.size()];

        // 使用优先队列维护当前各堆最小元素
        PriorityQueue<PileNode> pq = new PriorityQueue<>();
        for (int i = 0; i < piles.size(); i++) {
            if (!piles.get(i).isEmpty()) {
                pq.offer(new PileNode(piles.get(i).get(0), i));
                positions[i] = 1;
            }
        }

        while (!pq.isEmpty()) {
            PileNode min = pq.poll();
            result[idx++] = min.value;

            int pIdx = min.pileIndex;
            if (positions[pIdx] < piles.get(pIdx).size()) {
                pq.offer(new PileNode(piles.get(pIdx).get(positions[pIdx]), pIdx));
                positions[pIdx]++;
            }
        }

        return result;
    }

    private static int findPile(List<List<Integer>> piles, int num) {
        int left = 0, right = piles.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            int top = piles.get(mid).get(piles.get(mid).size() - 1);
            if (top < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 优先队列节点
     */
    private static class PileNode implements Comparable<PileNode> {
        int value, pileIndex;

        PileNode(int value, int pileIndex) {
            this.value = value;
            this.pileIndex = pileIndex;
        }

        @Override
        public int compareTo(PileNode other) {
            return Integer.compare(this.value, other.value);
        }
    }

    /**
     * 排序结果封装
     */
    public static class SortResult {
        public int[] sorted;
        public List<List<Integer>> piles;
        public List<String> steps;

        SortResult(int[] sorted, List<List<Integer>> piles, List<String> steps) {
            this.sorted = sorted;
            this.piles = piles;
            this.steps = steps;
        }
    }
}

主程序入口

/**
 * 耐心排序与LIS算法主程序
 */
public class PatienceSortingDemo {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

        System.out.println("原始数组: " + Arrays.toString(arr));
        System.out.println();

        // 1. 耐心排序演示
        System.out.println("=== 耐心排序 ===");
        PatienceSortingExtended.SortResult result = 
            PatienceSortingExtended.sortWithTrace(arr);

        System.out.println("分堆步骤:");
        for (String step : result.steps) {
            System.out.println("  " + step);
        }

        System.out.println("\n最终牌堆:");
        for (int i = 0; i < result.piles.size(); i++) {
            System.out.println("  堆" + i + ": " + result.piles.get(i));
        }

        System.out.println("\n排序结果: " + Arrays.toString(result.sorted));
        System.out.println("牌堆数量（= LIS长度）: " + result.piles.size());

        // 2. LIS求解
        System.out.println("\n=== 最长递增子序列 ===");
        int[] lis = LISSolver.findLIS(arr);
        System.out.println("LIS序列: " + Arrays.toString(lis));
        System.out.println("LIS长度: " + LISSolver.lengthOfLIS(arr));

        // 3. LDS求解
        System.out.println("\n=== 最长递减子序列 ===");
        int[] lds = LISSolver.findLDS(arr);
        System.out.println("LDS序列: " + Arrays.toString(lds));

        // 4. LCIS求解
        System.out.println("\n=== 最长连续递增子序列 ===");
        int[] lcis = LISSolver.findLCIS(arr);
        System.out.println("LCIS序列: " + Arrays.toString(lcis));

        // 5. 性能测试
        System.out.println("\n=== 性能测试 ===");
        int[] largeArr = generateRandomArray(100000);

        long start = System.currentTimeMillis();
        int lisLen = LISSolver.lengthOfLIS(largeArr);
        long time = System.currentTimeMillis() - start;

        System.out.printf("10万元素的LIS长度: %d%n", lisLen);
        System.out.printf("计算耗时: %d ms%n", time);

        // 对比O(n^2)的DP解法
        start = System.currentTimeMillis();
        int lisLenDP = lengthOfLIS_DP(largeArr);
        long timeDP = System.currentTimeMillis() - start;

        System.out.printf("DP解法耗时: %d ms%n", timeDP);
        System.out.printf("耐心排序优化比: %.1fx%n", (double) timeDP / time);
    }

    /**
     * O(n^2)的DP解法（用于对比）
     */
    private static int lengthOfLIS_DP(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    private static int[] generateRandomArray(int n) {
        Random rand = new Random(42);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(n);
        }
        return arr;
    }
}

算法复杂度分析

其中k为牌堆数量，n为数组长度。最坏情况下k=n，因此完整复杂度为O(n log n)。

总结

本文通过Java实现了耐心排序算法及其在最长递增子序列问题上的应用，核心要点包括：

• 二分查找优化使每次放牌操作降至O(log k)
• tails数组技巧将LIS问题空间复杂度优化至O(n)
• K路归并通过优先队列高效合并所有牌堆
• 前驱指针追踪支持完整LIS序列的重建

读者可以尝试扩展耐心排序以处理自定义比较器、求解最长公共子序列（LCS）的变体，或将该算法应用于股票买卖、任务调度等实际场景中的序列优化问题。