Day2-数组2023.9.15

Leetcode977 有序数组的平方

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

初解

我还是不能想到暴力解法之外的，对某个问题的最优复杂度也没有概念。就算提示我是用指针，我也想不到思路。
现在我知道的指针主要有快慢指针和双向指针。
受昨天那个原地换位置的影响，我也下意识没有想到新开一个数组。

看完解答

思路很简单：开一个新的数组，依次放进最大的数。最大的数必然在两侧（绝对值最大）。每次放进一个数，左右指针移动即可。
实现也很简单我一次就过了。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len=nums.size();
        int l=0,r=len-1;
        // 最大的一定在两头。
        vector<int> res;
        res.resize(len);
        int p=len-1;
        while(p>=0&&l<=r){
            if(nums[l]*nums[l]>nums[r]*nums[r]){
                res[p--]=nums[l]*nums[l];
                l++;
            }else{
                res[p--]=nums[r]*nums[r];
                r--;
            }
        }
        return res;
    }
};