题目：有序数组的平方

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

示例 1：

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

示例 2：

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

提示：

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

来源：力扣（LeetCode）第977题

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

分析：

这道题的方法有两种，一种最简单，先计算，再排序。第二种用双指针做到一遍遍历解答。

思路：

• 由于数组是按照递增的顺序增长的，因此所有的正数都是递增的，所有的负数加上绝对值都是递减的。
• 我们用两个指针i和j，i从前往后遍历，j从后往前遍历。
• i遇到正数就停下来，j遇到负数就停下来，然后比较他们两谁小，小的那个放到ans答案中。
• 然后就把放入答案中的那个指针往后前移。
• 最后退出循环，但是可能有一个指针并没有移到终点，因此要在循环结束后去判断两个指针的情况，把指针后面的值都加到ans中去。
• 最后得到答案。

代码：

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        i = 0
        j = len(A) - 1
        ans = []
        while i < len(A) and j >= 0:  # 主循环
            while i < len(A) and A[i] < 0:  # 遍历到第一个正数
                i += 1
            while j >= 0 and A[j] >= 0:  # 遍历到第一个负数
                j -= 1
            if i < len(A) and j >= 0:  # 谁小就把谁加进来
                if A[i] ** 2 > A[j] ** 2:
                    ans.append(A[j] ** 2)
                    j -= 1
                else:
                    ans.append(A[i] ** 2)
                    i += 1
        while i < len(A):  # 如果i没有到遍历完吧i加进去
            ans.append(A[i] ** 2)
            i += 1
        while j >=0:  # j没有到头把j加进去
            ans.append(A[j] ** 2)
            j -= 1
        return ans

• 简单暴力法

  class Solution:
  def sortedSquares(self, A: List[int]) -> List[int]:
      return sorted(x * x for x in A)
  

复杂度分析：

• 双指针法：
  • 时间复杂度：O(n) n 为数组长度
  • 空间复杂度：O(n)
• 暴力法：
  • 时间复杂度：O(nlogn) n为数组长度
  • 空间复杂度：O(n)

总结：

• 双指针法在解数组这一块的问题时是一个不错的方法。
• 一段递增的数，如果有负数那么负数的绝对值是递减的。反向遍历就能使其递增。