# 資訊

:::info
- Question: 977. Squares of a Sorted Array
- From: Leetcode Daily Challenge 2024.03.02
- Difficulty: Easy
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

> Example 1:
:::success
- Input: `nums = [-4,-1,0,3,10]`
- Output: `[0,1,9,16,100]`
- Explanation: After squaring, the array becomes `[16,1,0,9,100]`. After sorting, it becomes `[0,1,9,16,100]`.
:::

> Example 2:
:::success
- Input: `nums = [-7,-3,2,3,11]`
- Output: `[4,9,9,49,121]`
:::

> Constraints:
:::success
- $1$ <= `nums.length` <= $10^4$
- $-10^4$ <= `nums[i]` <= $10^4$
- `nums` is sorted in non-decreasing order.
:::

> Follow up: Squaring each element and sorting the new array is very trivial, could you find an $O(n)$ solution using a different approach?

---

# 解法

## 概念

這題 brute force 就是 follow up 叫我們不要做的方法，也就是先做完平方再 sorting，的確這樣很慢，但 $O(n)$ 是跑不掉的

這邊我給出兩種不同解法，我第一個直覺想到的辦法是 heap，因為讀取每一個 element 做平方是不可避免的，所以應該在 sorting 上下功夫，不要做 sorting 就要在 push 的時候做到，所以我打算用 push 的方法直接 push 進去就依照順序，到時候 return 就沒問題了

這個方唯一要注意是 heap 本身還是用 list 儲存，只是會有一些資訊告訴他 pop 順序，所以要拿到 heap 結構的順序要一個一個 pop 出來組成的 list 才會是答案，也是 heap 做 sort 的方法

另一個就是這題的考點：two pointers

在插入 list 這件事情可以動手腳，因為 `nums` 本身也有排序過，所以可以確定兩端平方後一定會是最大值，可以從兩端開始 append，直到回到中心，最後因為 append 順序是由大到小，到時候再 reverse 就好了，two pointers 解也是標準 $O(n)$

## 程式碼

> Heap 解

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        heap = []
        for e in nums:
            heapq.heappush( heap, e*e )
        return [ heapq.heappop( heap ) for i in range( len( nums ) ) ]

> Two pointers 解

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        res = []
        l = 0
        r = len( nums ) - 1

        while l <= r:
            if abs( nums[l] ) <= abs( nums[r] ):
                res.append( nums[r] * nums[r] )
                r -= 1
            else:
                res.append( nums[l] * nums[l] )
                l += 1
        
        return res[::-1]

> Brute force 解

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

---

# 複雜度

時間空間都是 $O(n)$，但不知道為什麼時間壓不下來，試了三個方法都一樣