题目

力扣题目链接

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

  1. 输入：nums = [-4,-1,0,3,10]
  2. 输出：[0,1,9,16,100]
  3. 解释：平方后，数组变为 [16,1,0,9,100]
  4. 排序后，数组变为 [0,1,9,16,100]

示例 2：

  1. 输入：nums = [-7,-3,2,3,11]
  2. 输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

思路

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，一个指向起始位置，另一个指向终止位置。

定义一个新数组，和题目给的数组一样的大小，让一个指针指向终止位置，倒序填充。

答案

Java

倒序填充

// 双指针 - 倒序填充
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] answer = new int[nums.length];

        int leftIndex = 0, rightIdex = nums.length - 1;

        // 从 answer 的最后一个元素开始向前填充, 数值具有递减的特征
        for (int i = nums.length - 1; i >= 0; i--) {
            // 比较 nums[leftIndex] 与 nums[rightIdex] 的绝对值大小
            if (f(nums[leftIndex], nums[rightIdex])) {
                // nums[leftIndex] 的绝对值比 nums[rightIdex] 大
                answer[i] = nums[leftIndex] * nums[leftIndex];
                leftIndex++;
            } else {
                // nums[rightIdex] 的绝对值比 nums[leftIndex] 大
                answer[i] = nums[rightIdex] * nums[rightIdex];
                rightIdex--;
            }
        }

        return answer;
    }

    // a 的绝对值是否比 b 大
    public boolean f(int a, int b) {
        if (a < 0) a *= -1;
        if (b < 0) b *= -1;
        return a > b;
    }
}

REF

https://leetcode-cn.com/problems/squares-of-a-sorted-array
https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/dai-ma-sui-xiang-lu-shu-zu-ti-mu-zong-ji-1rtz/