977. Squares of a Sorted Array

題目網址：https://leetcode.cn/problems/squares-of-a-sorted-array/

題意：給一 sorted array nums, 求每個數字平方所組成的 sorted array。

Solution：

想法：利用 two pointers

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        const int n = nums.size();
        int left = 0, right = n - 1;
        vector<int> res(n, 0);

        for (int i = n - 1; i >= 0; --i) { // res 從後面往前填(先填大的)
            if (abs(nums[left]) > abs(nums[right])) {
                res[i] = nums[left] * nums[left];
                ++left;
            } else {
                res[i] = nums[right] * nums[right];
                --right;
            }
        }

        return res;
    }
};

• time：$O(n)$ ➔ 遍歷 nums
• space：$O(n)$ ➔ 扣除返回的 array, 只需常數空間