[数据结构与算法]LeetCode第977题 有序数组的平方

1. 算法
   双指针
2. 核心思想
   这道题其实最简单的思路是直接平方以后，找个排序算法一排就可以，可以直接用快排。但是如果要求使用时间复杂度O（n）的算法，那就不能用排序算法，因为即便是快排，时间复杂度也要O(nlogn)。所以要利用非递减顺序这一条件。
   整个数组在平方后以第一个出现的正数为界，前半部分为逆序，后半部分为正序。可以令第一个指针指向正数前面的数字，第二个指针指向第一个正数，依次比较，存入新的数组中。
   如果为全正数数组，直接返回；全负数数组，颠倒顺序返回。
3. 代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int sign = -1;
        for(int i = 0;i< nums.length;i++){
            if(nums[i] >= 0 && sign == -1) sign = i;
            nums[i] = (int)Math.pow(nums[i],2);
            
        }
        if(sign == 0) return nums;
        int[] result = new int[nums.length];
        if(sign == -1){
            for(int i = 0;i< nums.length;i++){
                result[i] = nums[nums.length-1-i];
            }
            return result;
        }

        int i = sign-1,j = sign,k = 0;

        while(i >= 0 || j < nums.length){

            if(i < 0){
                result[k++] = nums[j++];
            }else if(j >= nums.length){
                result[k++] = nums[i--];
            }else if(nums[i] >= nums[j]){
                result[k++] = nums[j++];
            }else{
                result[k++] = nums[i--];
            }
        }

        return result;


    }
}