977. Squares of a Sorted Array

https://leetcode.com/problems/squares-of-a-sorted-array/

solution

• 直接法

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

时间复杂度：O(nlog(n)) 空间复杂度：O(n)

• 双指针

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l = 0
        r = len(nums) - 1
        res = []
        while r >= l:  # 注意小于等于
            r2 = nums[r] ** 2
            l2 = nums[l] ** 2
            if r2 > l2:
                res.append(r2)
                r -= 1
            else:
                res.append(l2)
                l += 1
        return res[::-1]

时间复杂度：O(n) 空间复杂度：O(n)