有序数组的平方

题目：

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

解题方法：

这道题如果用排序的话，其实写起来还是挺简单的，遍历一遍做平方处理，然后直接调用排序函数就得到结果了，测试了一下，反正没超时。但是结果肯定不满意啦，所以做了一些改进，主要思路如下：

• 遍历，平方处理；
• 找到数组的最小值所在位置，因为在平方之前已经是非递减的，所以平方之后，最小值就出现在：A[i]<A[i+1]第一次出现的位置。
• 然后就是从最小值两边开始进行排序，在最小值坐标是递减的数组，右边是递增的数组，所以遍历完两边的数组就完成了排序。

代码和结果：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int len=A.size();
        vector<int> B(len);
        for(int i=0;i<len;i++)
        {
            A[i]=A[i]*A[i];
        }
        int midx=len-1;
        for(int i=0;i<len-1;i++)
        {
            if(A[i]<A[i+1])
            {
                midx=i;
                break;
            }
        }
        
        int m=midx-1;
        int n=midx+1;
        B[0]=A[midx];
        int k=1;
        while(m>=0&&n<len)
        {
            if(A[m]<A[n])
            {
                B[k]=A[m];
                m--;
                k++;
            }
            else
            {
                B[k]=A[n];
                n++;
                k++;
            }
        }

        while(m>=0)
        {
            B[k]=A[m];
            m--;
            k++;
        }
        while(n<len)
        {
            B[k]=A[n];
            n++;
            k++;
        }

        return B;
    }
};

运行结果:

原题链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array/