1 题目描述

977. 有序数组的平方要求给定一个按非递减顺序排列的整数数组 nums，返回一个新的数组，其中每个元素都是原数组中对应元素的平方，并且新数组也需要是非递减顺序排列的。

2 解题思路

这个问题的关键在于原数组中的负数和正数部分。对于非负数来说，它们的平方会保持原有的顺序；而对于负数来说，由于平方后会变成正数，所以可能会改变原有的顺序。因此，我们可以考虑使用双指针法来解决这个问题。

• 初始化两个指针 left 和 right 分别指向数组的起始位置和末尾位置。
• 使用第三个指针 k 指向新数组的末尾。
• 比较 nums[left] 和 nums[right] 平方后的大小：
  • 如果 nums[left] * nums[left] 大于 nums[right] * nums[right]，则将 nums[left] 的平方放入新数组的末尾，并将 left 向右移动一位；
  • 否则，将 nums[right] 的平方放入新数组的末尾，并将 right 向左移动一位。
• 重复上述步骤直到 left 和 right 指针相遇或交错。

这种方法能够确保数组中的元素按照非递减顺序排列，因为每次都是选择较大的平方值放到新数组的末尾，这样就避免了对整个数组进行额外的排序操作。

3 Java 代码实现

1public class Solution {
2    public int[] sortedSquares(int[] nums) {
3        int[] ans = new int[nums.length];
4        int left = 0;
5        int right = nums.length - 1;
6        int k = nums.length - 1;  // // 新数组的右指针
7        while (left <= right) {
8            if (nums[left] * nums[left] > nums[right] * nums[right]) {
9                ans[k--] = nums[left] * nums[left];
10                left++;
11            } else {
12                ans[k--] = nums[right] * nums[right];
13                right--;
14            }
15        }
16        return ans;
17    }
18}

4 注意事项

• 双指针：使用双指针技术，其中 left 指针指向数组的开头，而 right 指针指向数组的结尾。
• 原地修改：虽然本题允许创建一个新的数组来存储结果，但双指针技术可以高效地完成任务。
• 从后往前填充：新数组从后往前填充，以确保最后得到的数组是非递减排序的。