1. 有序数组的平方
题目：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
思路：左右指针比较，把平方大的结果填进新数组尾部，index向前滑
笔记：
vector是一个动态的序列容器，相当于一个size可变的数组。
初始化向量容器：
//对容量为n的动态数组的所有元素赋值为val
vector<int>arr(n,val)
//也可以写
vector<int>arr(n)
C++：
// 时间复杂度：O(n)
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result(nums.size(), 0);
int k = nums.size() - 1;
for (int i = 0, j = nums.size() - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
result[k--] = nums[i] * nums[i];
i++;
} else {
result[k--] = nums[j] * nums[j];
j--;
}
}
return result;
}
};
Python：
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
result = [0] * n
i, j, k = 0, n-1, n-1
while i <= j:
ls = nums[i] ** 2
rs = nums[j] ** 2
if(ls > rs):
result[k] = ls
i += 1
else:
result[k] = rs
j -= 1
k -= 1
return result
