leetcode🧑‍💻 977. 有序数组的平方

数据结构与算法双指针 #算法 #双指针 #对撞指针

2022-05-16 | 2024-04-11 | 223 | 1 分钟

977. 有序数组的平方

对撞指针

解题思路

使用两个指针 left、right 分别指向数组的 第一位 和 最后一位 ，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针；

这种方法无需处理某一指针移动至边界的情况；

图解

复杂度

时间复杂度：O(n)，其中 n 是数组 nums 的长度；
空间复杂度：O(1)，除了存储答案的数组以外，只需要维护常量空间；

代码实现

function sortedSquares(nums: number[]): number[] {
    let left = 0;
    let right = nums.length - 1;
    let res = new Array(right);
    // 初始索引
    let inx = right;

    while (left <= right) {
        // 获取 left、right 的平方
        let l = nums[left] ** 2;
        let r = nums[right] ** 2;

        if (l > r) {
            res[inx] = l;
            left++;
        } else {
            res[inx] = r;
            right--;
        }

        inx--;
    }

    return res;
};