有序数组的平方

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

大致看了下该题在力扣的评论，先平方，然后再sort的解题代码还很多。其实这应该不是本题的题意，要不然没必要强调是非递减顺序排序。在这里三种情况：纯正数数组，纯负数数组，正负混合的数组。

对于纯正数数组直接代码如下：

        int length = A.length;
		int res[] = new int[length];
		//都是正数,含0
		if(A[0]>=0) {
			for(int i=0;i<length;i++) {
				res[i]= (int) Math.pow(A[i], 2);
			}
			return res;
		}

对于纯负数数组，算法也很简单：

int length = A.length;
int res[] = new int[length];
	
  //都是负数，含0
	if(A[length-1]<=0) {
		System.out.print( "0000 ");
		int index = length-1;
		for(int i=0;i<length;i++) {
			res[index--]= (int) Math.pow(A[i], 2);
		}
		return res;
	}

那么本体的考点应该就是第三种情况的算法，即正负混合的数组怎么解答本题。
其实解题思想也很简单：因为是原数组是非递减顺序排序的，比如[-4,-1,0,3,10]，那么平方过后就是[16,1,0,9,100].
如果都是正数的话，那么最右边的数肯定是最大的，其平方也是最大的，但是包含了负数的话，平方后谁大那就说不定了。所以在这里采用了双指针法，从两边逐次对比，谁大取谁：

	int left = 0, right = length - 1;
		int resIndex = length - 1;
		while (resIndex >= 0) {
			int leftSquare = (int) Math.pow(A[left], 2);
			int rightSquare = (int) Math.pow(A[right], 2);
			if (leftSquare >= rightSquare) {
				res[resIndex] = leftSquare;
				left++;
			} else {
				res[resIndex] = rightSquare;
				right--;
			}
			resIndex--;
		}

		return res;

完整的算法如下：

	public static int[] sortedSquares2(int[] A) {
		int length = A.length;
		int res[] = new int[length];
		//说明都是正数
		if(A[0]>=0) {
			for(int i=0;i<length;i++) {
				res[i]= (int) Math.pow(A[i], 2);
			}
			return res;
		}
		
		//都是负数
		if(A[length-1]<=0) {
			int index = 0;
			for(int i=0;i<length;i++) {
				res[index++]= (int) Math.pow(A[i], 2);
			}
			return res;
		}
		
		//正负都有的情况
		int left = 0, right = length - 1;
		
		int resIndex = length - 1;

		while (resIndex >= 0) {
			int leftSquare = (int) Math.pow(A[left], 2);
			int rightSquare = (int) Math.pow(A[right], 2);
			// 将最大值放在后面
			if (leftSquare >= rightSquare) {
				res[resIndex] = leftSquare;
				left++;
			} else {
				res[resIndex] = rightSquare;
				right--;
			}
			resIndex--;
		}

		return res;
	}

但是对于第三种，其效率还可以做一个小小的优化，因为在left或者right的值没有变换的情况下会造成leftSquare或者rightSquare 平方的重复运算，可以小小修改一下：

int left = 0, right = length - 1;
		int resIndex = length - 1;

       //在while循环外计算一次
		int leftSquare = (int) Math.pow(A[left], 2);
		int rightSquare = (int) Math.pow(A[right], 2);
		
		//判断是左边的数据大还是右边的数据大
		boolean fromLeft = false;
		
		while (resIndex >= 0) {
		   //谁大取谁
			if (leftSquare >= rightSquare) {
				res[resIndex] = leftSquare;
				left++;
				fromLeft = true;
			} else {
				res[resIndex] = rightSquare;
				right--;
				fromLeft = false;
			}
			
			resIndex--;
			//防止数组越界
			if(left>length-1) {
				break;
			}
			
			//防止重复对leftSquare或者rightSquare 计算
			if (fromLeft) {
				leftSquare = (int) Math.pow(A[left], 2);
			} else {
				rightSquare = (int) Math.pow(A[right], 2);
			}

		}//end while

		return res;