LeetCode 977.有序数组的平方

LeetCode 977.有序数组的平方

**题目描述：**非递减数组nums，将各元素平方按非递减顺序排列，返回新数组

• 思路：
  • nums元素组成可能为：①全正；②全负；③有正有负；
  • 对于有正有负的情况，需要比较负数平方与正数平方，才能决定在新数组中的位置
  • 用一个指针扫描负数，一个指针扫描正数，①②可合并到③（一个指针始终未更新）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ans(nums.size(), 0);
        int left = 0;
        int right = nums.size() - 1;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {//保证有序
                ans[i] = nums[left] * nums[left];//最大的在后面，升序
                left++;
            }
            else {
                ans[i] = nums[right] * nums[right];
                right--;
            }
        }
        return ans;
    }
};