LeetCode 977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题
分析：
不能忽略题干的信息：数组本身为非递减的顺序，由此可分为三种情况讨论：
1、数组元素全都大于等于0，此时返回数组元素自身的平方即可
2、数组元素全都小于等于0，此时数组元素自身平方后，需要逆序排列
3、数组元素小于0，大于0的部分都有，此时结果中的最大值为两端某个元素的平方
解法一：暴力排序
暴力排序忽略了nums本身就是非递减顺序这一条件，将nums的元素平方后，用STL标准库中的排序算法 sort(beg, end) 进行排序即可
代码如下：
for(int i = 0; i < nums.size(); i++){ nums[i] = nums[i] * nums[i]; } sort(nums.begin(), nums.end()); //快速排序 return nums; 解法二：双指针法 设置左右两个指针，分别指向nums的两端，不管nums中元素的正负情况，最终结果的最大元素始终在nums的两端取得 如动画所示（https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html#%E5%8F%8C%E6%8C%87%E9%92%88%E6%B3%95）：代码如下：
int left = 0, right = nums.size() - 1; int index = nums.size() - 1; vector