Java straightforward heap O(N)
Time: \nO(N * lg4 * 2) == O(N), if N > 8;\nO(NlgN) if N <= 8;\nspace: O(1);\nJust calculate smallest 4 numbers and largest 4 numbers, and compare the difference
Time: \nO(N * lg4 * 2) == O(N), if N > 8;\nO(NlgN) if N <= 8;\nspace: O(1);\nJust calculate smallest 4 numbers and largest 4 numbers, and compare the differences (see getDiff for detail.\n```\nclass Solution {\n    public int minDifference(int[] nums) {\n        if (nums.length < 5) return 0;\n        if (nums.length <= 8) return getDiff(nums, true);\n        PriorityQueue<Integer> top4 = new PriorityQueue<>(), bot4 = new PriorityQueue<>((a, b) -> b - a);\n        for (int n : nums) {\n            top4.offer(n);\n            bot4.offer(n);\n            if (top4.size() > 4) top4.poll();\n            if (bot4.size() > 4) bot4.poll();\n        }\n        int[] arr = new int[8];\n        for (int l = 3, r = 4; l >= 0 && r < 8; l--, r++) {\n            arr[l] = bot4.poll();\n            arr[r] = top4.poll();\n        } \n        return getDiff(arr, false);\n    }\n    \n    private int getDiff(int[] arr, boolean needSort) {\n        if (needSort) Arrays.sort(arr);\n        int res = Integer.MAX_VALUE, n = arr.length;\n        for (int i = 0; i < 4; i++) {\n            res = Math.min(res, arr[n - (4 - i)] - arr[i]);\n        }\n        return res;\n    }\n}\n```
[]