给你一个按 非递减顺序 排序的整数数组nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
暴力解法这里就不讲解了，重点是双指针法。
方法一 ：双指针（一）我们从题目可以知道，数组是按升序排列的，可以有以下三种情况：
这样看来，我们可以先找到数组中负数和非负数的分界线，记为flag，分界线左边为负数，非负数的右边为非负数
由图可知：
当将原数组的数据平方之后，nums[0] ~ nums[flag]是单调递减的， nums[flag+1] ~ nums[nums.size()-1]是单调递增的
具体实现：
class Solution {
public:
vectorsortedSquares(vector& nums) {
int n = nums.size();
int flag= -1;
//找到最后一个负数的位置
for (int i = 0; i < n; ++i){
if (nums[i] < 0){
flag= i;
} else {
break;
}
}
//结果数组
vectorans;
//i为最后一个数组的位置，j为第一个>=0的位置
int i = flag, j = flag+ 1;
while (i >= 0 || j < n){
//此时小于0的数已经全部放进结果集，只需看j的
if (i < 0){
ans.push_back(nums[j] * nums[j]);
++j;
}
//此时j那边的数已经全部遍历完
else if (j == n){
ans.push_back(nums[i] * nums[i]);
--i;
}
//i的平方小于j的平方
else if(nums[i] * nums[i] < nums[j] * nums[j]){
ans.push_back(nums[i] * nums[i]);
--i;
}
//i的平方大于j的平方
else{
ans.push_back(nums[j] * nums[j]);
++j;
}
}
return ans;
}
};
复杂度分析：
时间复杂度：O(n)，其中 nn是数组nums 的长度。
空间复杂度：O(1)，除了存储答案的数组以外，我们只需要维护常量空间。
方法二 ：双指针(二）数组其实是有序的， 只不过负数平方之后有可能会成为大数，从而变成了先递减后递增的数组。那么数组平方的大值就在数组的两端，不是在最左边就是最右边，而不可能在中间。此时我们依然可以考虑双指针法。
class Solution {
public:
vectorsortedSquares(vector& nums) {
int n = nums.size();
vectorans(n);
int i = 0;//数组的起始位置
int j = n - 1;//数组的终止位置
int k = n - 1;//ans数组插入数据的位置
while(i<=j)
{
if(nums[i]*nums[i] >nums[j]*nums[j])
{
ans[k] = nums[i]*nums[i];
i++;
}
else
{
ans[k] = nums[j]*nums[j];
j--;
}
--k;
}
return ans;
}
}; 复杂度分析：
时间复杂度：O(n)，其中 nn 是数组 nums 的长度。
空间复杂度：O(1)，除了存储答案的数组以外，我们只需要维护常量空间。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
