---

一、题目链接

链接: 977. 有序数组的平方

---

二、参考代码

简单思路：赋值给新的数组然后排序

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int>out;for(int i=0;i<nums.size();i++){int in = nums[i]*nums[i];out.push_back(in);}sort(out.begin(),out.end());return out;}
};

新思路：双指针，一个指针从数组的开始，另一个指针从数组的末尾，比较两个指针对应的元素的绝对值，然后将较大的那个元素的平方放到结果数组的末尾，然后移动指针，直到两个指针相遇。这样可以保证结果数组是有序的，并且时间复杂度为 O(n)。

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int n = nums.size();vector<int> out(n, 0);int left = 0, right = n - 1, pos = n - 1;while (left <= right) {if (abs(nums[left]) > abs(nums[right])) {out[pos] = nums[left] * nums[left];left++;} else {out[pos] = nums[right] * nums[right];right--;}pos--;}return out;}
};

---

三、所思所悟

提供的双指针法适用于非递减数组，因为它依赖于绝对值较大的数在数组的两端这一特性。
如果数组不是非递减的，我们需要使用不同的方法来确保结果数组是有序的。

对于任意数组，我们仍然可以使用排序的方法，但是需要先对数组中的每个元素进行平方，然后再进行排序。这种方法的时间复杂度是 O(n^2) 的操作加上 O(n log n) 的排序操作，即 O(n log n)。