题目：

977. 有序数组的平方

难度简单742收藏分享切换为英文接收动态反馈

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= nums.length <= 104

• -104 <= nums[i] <= 104

• nums 已按 非递减顺序 排序

 

进阶：

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

第一种对法：

class Solution {

public:

    vector<int> sortedSquares(vector<int>& nums) {

        vector<int> s(nums.size(),0);

        int first,last,index=nums.size()-1;

        first=0;last=nums.size()-1;

        while(first<=last){

            if(nums[first]*nums[first]>nums[last]*nums[last]){

                s[index--]=nums[first]*nums[first];

                first++;

            }else{

                s[index--]=nums[last]*nums[last];

                last--;

            }

        }

        return s;

    }

};

创建一个新数组，用来存储答案，在末尾和开头分别放置一个指针，两个指针相互靠近，每次比较将平方大的放进答案数组，最后返回；

时间复杂度O(n);

空间复杂度O(n);

双指针算法