Java递归栈溢出问题：求数组右侧更小元素数的代码重构方案

原代码的问题在于countSmaller方法的递归深度等于数组中当前元素右侧的元素数量，当数组规模较大（比如长度超过几千）时，递归深度会超过JVM的默认栈容量，从而抛出StackOverflowError。以下是两种重构方案：

方案一：将递归改为迭代（简单直接，解决栈溢出） #

把递归遍历右侧元素的逻辑替换成普通的for循环，完全消除递归调用，彻底避免栈溢出问题。代码如下：

public class Smaller {
    public static int[] smaller(int[] unsorted) {
        int[] result = new int[unsorted.length];

        for (int i = 0; i < unsorted.length; i++) {
            int count = 0;
            // 遍历当前元素右侧的所有元素，统计更小的数量
            for (int j = i + 1; j < unsorted.length; j++) {
                if (unsorted[j] < unsorted[i]) {
                    count++;
                }
            }
            result[i] = count;
        }

        return result;
    }
}

说明：该方案逻辑简单，快速解决栈溢出，但时间复杂度仍为O(n²)，处理超大数组（如10万级以上）时运行速度会较慢。

方案二：使用归并排序优化（高效处理大数组） #

通过归并排序的思路，在排序过程中统计每个元素右侧更小的元素数量，时间复杂度降至O(n log n)，同时递归深度仅为log₂n（比如100万长度的数组，递归深度仅20左右），远低于JVM栈容量，不会出现栈溢出。代码如下：

public class Smaller {
    static class Element {
        int value;
        int originalIndex;

        Element(int value, int originalIndex) {
            this.value = value;
            this.originalIndex = originalIndex;
        }
    }

    public static int[] smaller(int[] unsorted) {
        int length = unsorted.length;
        int[] result = new int[length];
        Element[] elements = new Element[length];

        // 将数组元素与原始索引绑定
        for (int i = 0; i < length; i++) {
            elements[i] = new Element(unsorted[i], i);
        }

        mergeSortAndCount(elements, 0, length - 1, result);
        return result;
    }

    private static void mergeSortAndCount(Element[] elements, int left, int right, int[] result) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSortAndCount(elements, left, mid, result);
        mergeSortAndCount(elements, mid + 1, right, result);
        merge(elements, left, mid, right, result);
    }

    private static void merge(Element[] elements, int left, int mid, int right, int[] result) {
        Element[] temp = new Element[right - left + 1];
        int i = left;
        int j = mid + 1;
        int tempIndex = 0;

        // 合并时统计右侧比左侧元素小的数量
        while (i <= mid && j <= right) {
            if (elements[i].value > elements[j].value) {
                // 左侧当前元素比右侧当前元素大，那么左侧当前元素及后续所有元素都比右侧当前元素大
                result[elements[i].originalIndex] += right - j + 1;
                temp[tempIndex++] = elements[i++];
            } else {
                temp[tempIndex++] = elements[j++];
            }
        }

        // 处理剩余的左侧元素
        while (i <= mid) {
            temp[tempIndex++] = elements[i++];
        }

        // 处理剩余的右侧元素
        while (j <= right) {
            temp[tempIndex++] = elements[j++];
        }

        // 将临时数组复制回原数组
        System.arraycopy(temp, 0, elements, left, temp.length);
    }
}

说明：该方案在解决栈溢出的同时，大幅提升了大数组的处理效率，适合需要处理大规模数据的场景。如果极端情况下仍担心递归栈溢出，可以将归并排序改为迭代实现，但递归版已经足够应对绝大多数场景。

内容的提问来源于stack exchange，提问作者Mark