【力扣】977. 有序数组的平方

977. 有序数组的平方

题目要求很简单，解题的逻辑也清晰，就是将数组做一个升序排序。但是注意，题目要求时间复杂度为 O(n)，这样就打消了调用 Java 库内置的排序方法的念头了。一般我们看到这种对时间复杂度有要求的题目，通常第一考虑的是用空间换时间，即用额外的存储来使得程序执行时间更短。所以几乎可以肯定这道题目需要额外开辟一个数组，即空间复杂度为 O(n)。

我相信大部分同学肯定能想到用双指针解题，但需要注意双指针指向的位置，可能部分同学会考虑从中间向外展开。

但其实这是题目给我们的诱导，题目给的例子只是恰好是一个先递减再递增的数组，且平方后的最小值正好在数组中间，因此这种方法要解题是比较费劲的，且编写出来的代码也不够优化。这时候可以考虑从两端向中间靠拢。只需要判断 nums[left] 与 nums[right] 大小，然后在存储进新的数组即可。

代码如下：

class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            nums[i] = (int)Math.pow(nums[i], 2);
        }
        int[] result = new int[nums.length];
        for(int i = result.length - 1, left = 0, right = nums.length - 1; i >= 0 && left <= right; i--) {
            if(nums[right] >= nums[left]) {
                result[i] = nums[right--];
            } else {
                result[i] = nums[left++];
            }
        }
        return result;
    }
}