977. 有序数组的平方
他给了一个有序数组，然后要你平方以后按照顺序排列，还要用O(n)时间复杂度。
首先，肯定不能平方了再去排序，快排时间复杂度O(nlogn)。这个数组本身含有排序信息，不要不去利用它。
一开始，我想到了线二分找数组的中间（正负分界的大概位置），从那里开始，往两遍开始平方，谁小谁先放进新数组：
cpp
class Solution {
public:
vector<int> sortedSquares(vector<int> &nums)
{
int i, j, n = nums.size();
findBorder(nums, i, j);
vector<int> res(n);
int k = 0;
while (i >= 0 || j < n) {
if (i < 0) {
res[k++] = nums[j] * nums[j];
j++;
continue;
}
if (j >= n) {
res[k++] = nums[i] * nums[i];
i--;
continue;
}
if (nums[i] * nums[i] > nums[j] * nums[j]) {
res[k++] = nums[j] * nums[j];
j++;
}
else {
res[k++] = nums[i] * nums[i];
i--;
}
}
return res;
}
private:
// 找到正负大概的分界点,O(log n)
void findBorder(const vector<int> &nums, int &i, int &j)
{
int l = 0, r = static_cast<int>(nums.size()) - 1, m;
while (l <= r) {
m = l + (r - l) / 2;
if (nums[m] > 0) {
r = m - 1;
}
else {
l = m + 1;
}
}
i = r;
j = l;
}
};这种确实是对的，但是这种明显写得太复杂了，不方便，两个边界也很难维护。
在ai的提示下，我知道可以换一种思路：为什么一定要从中间开始呢？可以直接从两边开始啊，和刚才倒着来，取更大的结果，倒序放进新数组里。这样只要看两个指针间的关系来决定循环终止条件，而且也不用事先找中间位置。
第二次：
cpp
class Solution {
public:
vector<int> sortedSquares(vector<int> &nums)
{
int n = nums.size(), i = 0, j = n - 1, k = n - 1;
vector<int> res(n);
while (i <= j) {
int i_square = nums[i] * nums[i], j_square = nums[j] * nums[j];
if (i_square > j_square) {
res[k--] = i_square;
i++;
}
else {
res[k--] = j_square;
j--;
}
}
return res;
}
};while (i <= j)解释：ij指的东西都是还没有被处理过的。i == j的时候，代表从左边来，这个数没有被处理过；从右边来，这个数也没有被处理过。所以整个数组就剩下它没有处理了，不能停。
最终，这个做法确实是比较标准的最优做法。