image.png

思路 這題目中文描述是真的2,非要反著描述, 非遞減順序的數(shù)組, 那不就是遞增的數(shù)組嗎

1. 需要思考的點(diǎn)就是 最小的負(fù)數(shù)平方之后會(huì)發(fā)生變化, 負(fù)負(fù)得正,可能變成最大數(shù)
2. 這樣其實(shí)我們需要兩個(gè)指針, 一個(gè)指向最左邊, 一個(gè)指向最右邊, 分別平方后,來(lái)比較他們的大小
3. 創(chuàng)建一個(gè)新的數(shù)組,大小和nums一樣, 創(chuàng)建一個(gè)索引k , 叢新數(shù)組的末位開(kāi)始 k = 新數(shù)組的最大索引值
4. 對(duì)比平方后的值, 如果if (nums[left] * nums[left] > nums[right] * nums[right]) 我們就將nums[left]的值放入新數(shù)組的最后面 k下標(biāo)對(duì)應(yīng)的位置 數(shù)組[k] = nums[left] *nums[left], left++ k--
5. if (nums[left] * nums[left] <= nums[right] * nums[right]) 將nums[right]放入新數(shù)組中k--, right向前移動(dòng)一位 right--
6. 當(dāng)left和right相遇時(shí), 是同一個(gè)數(shù), 剩下最后一位,放入新數(shù)組[k]即完成

    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length -1;
        int k = right;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                result[k--] = nums[left] * nums[left];
                left++;
            } else {
                result[k--] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }