有序数组的平方977

地址：https://leetcode.cn/problems/binary-search/description/?envType=problem-list-v2&envId=binary-search

题干

给你一个按 非递减顺序 排序的整数数组 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) 的算法解决本问题。

思路

乍一看是暴力题，全部乘方一遍，再写个排序（或者直接sort()）。

进阶要求O(n)，就是一遍遍历过，那我可以在乘方的时候排序吗？可以的，但是我们要注意使用二分思想，双指针。

怎么用？首先这道题不要忽略它的非递减状态，这个数组实际上是有序的，但是平方之后改变符号，原先的负数可能会很大。

我们用一个左指针放在最小负数，一个右指针放在最大正数，因为最大值不可能在中间，我们不需要纠结左右指针还该怎么放。

那么我们进行比对：左右指针开始移动，如果乘方后左指针指向值更大，进栈，左指针右移；反之右指针左移。移到中间的过程肯定是越来越小。

题解

暴力：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0;i<nums.size();++i){
            nums[i] = nums[i]*nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

双指针：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int lptr = 0;
        int numSize = nums.size();
        int rptr = numSize-1;
        int len = numSize-1;
        vector<int> result(numSize,0);
        while(lptr<=rptr){
            if(nums[lptr]*nums[lptr]<nums[rptr]*nums[rptr]){
                result[len--] = nums[rptr]*nums[rptr];
                rptr--;
            }else{
                result[len--] = nums[lptr]*nums[lptr];
                lptr++;
            }
        }
        return result;
    }
};