2019-05-19LeetCode977. 有序数组的平方

    def sortedSquares(self, A: List[int]) -> List[int]:
        neg=0
        while neg< (len(A)-1):
            if A[neg]>=0:break
            if A[neg] < 0 and A[neg + 1] >= 0: break
            neg+=1
        print(neg)
        pos=neg+1
        result=[]
        while(neg>-1 and pos<len(A)):
            if(A[neg]**2>=A[pos]**2):
                result.append(A[pos]**2)
                pos+=1
            else:
                result.append(A[neg]**2)
                neg-=1
        while(neg>-1):
            result.append(A[neg]**2)
            neg-=1
        while(pos<len(A)):
            result.append(A[pos]**2)
            pos+=1
        return result

1.难点在于考虑分解点在哪里，可能全小于0，可能全大于0

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        result=[0]*len(A)
        l,h=0,len(A)-1
        n=h
        while(l<=h):
            a=A[l]*A[l]
            b=A[h]*A[h]
            if(a>=b):
                result[n]=a
                l+=1
            else:
                result[n]=b
                h-=1
            n-=1
        return  result

这里的方法和合并两个有序数组一模一样，重点在于从大往小排序，逆向思维

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        result=collections.deque()
        l,h=0,len(A)-1
        n=h
        while(l<=h):
            a=A[l]*A[l]
            b=A[h]*A[h]
            if(a>=b):
                result.appendleft(a)
                l+=1
            else:
                result.appendleft(b)
                h-=1
            n-=1
        return  list(result)

同样的思路，使用collections里的deque，简化代码