方法一：暴力

时间复杂度：主要在排序的nlogn上

  2. //方法一：暴力
  3. func sortedSquares(nums []int) []int {
  4.     //输入的是一个有负数的非递减顺序的排序数组
  5.     ret := make([]int, len(nums))
  7.     //暴力：直接添加每一个元素的平方，然后进行排序
  8.     for i := 0; i < len(nums); i++ {
  9.         ret[i] = nums[i] * nums[i]
  10.     }
  12.     //最后对结果进行排序
  13.     sort.Ints(ret)
  15.     return ret
  16. }

方法二：双指针

思路：使用双指针l和r，开始时l指向负数的最右元素，r指向非负数中的最左元素，然后分别向左和向右移动
时间复杂度：O(n) 

func sortedSquares(nums []int) []int {


    //special case
    if len(nums) == 0 {
        return []int{}
    }

    arrayLength := len(nums)

    ret := make([]int, arrayLength)

    l, r := 0, 0
    for r < arrayLength {
        if nums[r] >= 0 {
            break
        }
        r++
    }

    l = r - 1

    //动态维护结果数组的下标
    i := 0

    //如果l和r都还有效
    for l >= 0 && r <= arrayLength-1 {
        if nums[l] * nums[l] < nums[r] * nums[r] {
            ret[i] = nums[l] * nums[l]
            l--
        } else {
            ret[i] = nums[r] * nums[r]
            r++
        }
        i++
    }

    //走到这里时，还剩余负数或者非负数这两侧的一侧
    for l >= 0 {
        ret[i] = nums[l] * nums[l]
        l--
        i++
    }

    for r <= arrayLength-1 {
        ret[i] = nums[r] * nums[r]
        r++
        i++
    }

    return ret
}