分治查找数组最值递归返回时Pair对象的min、max值是否保留

结论 #

每次递归返回到上一层调用方法时，Pair对象中存储的min、max值会被完全保留。

核心原因 #

• Java的参数传递规则中，基本类型是值传递，而对象类型传递的是引用的副本，所有递归调用里传入的Pair实例，实际都指向堆内存中同一个对象，不会额外生成拷贝。
• 任意一层递归对p.max、p.min的修改，都是直接修改堆中唯一实例的属性值，该修改结果是写入对象本身的，和当前递归方法执行完出栈销毁没有关联，上层调用拿到的始终是最新修改后的属性值。
• 对应这段代码的执行逻辑：左子数组递归执行结束返回时，p里已经存储了左子数组范围内统计到的最值，后续右子数组递归会直接在这个结果基础上继续更新。

原算法参考代码 #

// 封装整型最大最小值的Pair类
class Pair
{
    public int max, min;

    public Pair(int max, int min)
    {
        this.max = max;
        this.min = min;
    }
}

class Main
{
    // 分治法查找数组中最小和最大值的实现
    public static void findMinAndMax(int[] A, int left, int right, Pair p)
    {
        // 数组只剩一个元素的情况
        if (left == right)
        {
            if (p.max < A[left]) {
                p.max = A[left];
            }

            if (p.min > A[right]) {
                p.min = A[right];
            }

            return;
        }

        // 数组只剩两个元素的情况
        if (right - left == 1)
        {
            if (A[left] < A[right])
            {
                if (p.min > A[left]) {
                    p.min = A[left];
                }

                if (p.max < A[right]) {
                    p.max = A[right];
                }
            }
            else {
                if (p.min > A[right]) {
                    p.min = A[right];
                }

                if (p.max < A[left]) {
                    p.max = A[left];
                }
            }

            return;
        }

        // 找到中间位置拆分左右子数组
        int mid = (left + right) / 2;

        // 递归处理左子数组
        findMinAndMax(A, left, mid, p);

        // 递归处理右子数组
        findMinAndMax(A, mid + 1, right, p);
    }

    public static void main(String[] args)
    {
        int[] A = { 7, 2, 9, 3, 1, 6, 7, 8, 4 };

        // 初始化Pair：最大值初始为int最小值，最小值初始为int最大值
        Pair p = new Pair(Integer.MIN_VALUE, Integer.MAX_VALUE);
        findMinAndMax(A, 0, A.length - 1, p);

        System.out.println("数组最小元素为：" + p.min);
        System.out.println("数组最大元素为：" + p.max);
    }
}

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