• [ ] 977.有序数组的平方 :::info 前提：

    • 非降数组 ::: 代码：（详细注释）

      1. //暴力排序 O(n + nlogn)
      2. class Solution {
      3. public:
      4.   vector<int> sortedSquares(vector<int>& A) {
      5.       for (int i = 0; i < A.size(); i++) {
      6.           A[i] *= A[i];
      7.       }
      8.       sort(A.begin(), A.end()); // 快速排序
      9.       return A;
      10.   }
      11. };

      ```cpp //双指针算法 O(n) class Solution { public: vector sortedSquares(vector& A) {

        int k = A.size() - 1;
  vector<int> result(A.size(), 0);
  for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
      if (A[i] * A[i] < A[j] * A[j])  {
          result[k--] = A[j] * A[j];
          j--;
      }
      else {
          result[k--] = A[i] * A[i];
          i++;
      }
  }
  return result;

      } };

    ``` 分析：
    有序数组的平方 - 图1