更多精彩内容，请关注【力扣简单题】。

题目

难度：★☆☆☆☆
类型：数组

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

提示
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

示例

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

示例 2
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

解答

方案1：暴力求解

我们对输入数组中每个元素进行平方，然后对结果进行数组进行排序即可。

class Solution:
    def sortedSquares(self, A):
        return sorted(map(lambda x: x*x, A))

方案2：双指针

（参考官方解答）

我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分，指针 j 正向读取非负数部分。

那么，现在我们就在使用两个指针分别读取两个递增的数组了（按元素的平方排序）。接下来，我们可以使用双指针的技巧合并这两个数组。

class Solution(object):
    def sortedSquares(self, A):
        N = len(A)

        # 首先，我们找到负数和非负数的分界点j，代表最大的一个负数
        p = 0                           # 正数指针
        while p < N and A[p] < 0:
            p += 1

        n = p - 1

        ans = []
        while 0 <= n and p < N:
            if A[n]**2 < A[p]**2:       # 正数的平方比负数大
                ans.append(A[n]**2)     # 添加较小的平方数
                n -= 1
            else:
                ans.append(A[p]**2)
                p += 1

        # 如果还有剩余负数，继续添加
        while n >= 0:
            ans.append(A[n]**2)
            n -= 1

        # 如果还有剩余正数，继续添加
        while p < N:
            ans.append(A[p]**2)
            p += 1

        return ans

如有疑问或建议，欢迎评论区留言~