AlgoPressAppearance
0977-有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array
给你一个按 非递减顺序 排序的整数数组 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 <= 10^4
- 10^4 <= nums[i] <= 10^4
- nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
思路
因为原来数组是按照递减排序的，所以负数的平方会变大，一直到0，然后正数的平方依次递增。 因此从两边开始循环，将平方比较，将大的平方结果放到右边小的放到左边做下一次比较，这样循环结束的时候，最小的就在最左边。
参考代码
csharp
public class Solution {
//暴力法就是先做平方，再排序，略去
//基本思路： 原先就是有序数组，平方之后，就是负数变成正数了
//所以最大的数一定在两边，不在中间
//使用双指针，从两边分别往中间靠近，填入数组也从后往前
public int[] SortedSquares(int[] nums) {
int[] result = new int[nums.Length];
int left = 0;
int right = nums.Length - 1;
for(int i = nums.Length - 1; i>=0; i--){
if(nums[right] * nums[right] > nums[left] * nums[left]){
result[i] = nums[right] * nums[right];
right--;
}
else{
result[i] = nums[left] * nums[left];
left++;
}
}
return result;
}
}