### 题目

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]


Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]


### 二次函数的极值问题

left            right
|->           <-|
[9,    3,  15,  33]
|
| 极值x=-1.5
|
[-4,  -2,   2,   4]


#### 代码

class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
if (nums == null) { return null; }
int[] result = new int[nums.length];
//calculate
for (int i = 0; i < nums.length; i++) {
result[i] = function(nums[i],a,b,c);
}
//sort
int[] sorted = new int[nums.length];
int p = (a <= 0)? 0 : nums.length - 1; //a > 0，正漏斗。 a <= 0，倒漏斗。
for (int left = 0, right = nums.length-1; left <= right; ) {
if (a <= 0) {
sorted[p++] = (result[left] <= result[right])? result[left++] : result[right--];
} else {
sorted[p--] = (result[left] >= result[right])? result[left++] : result[right--];
}
}
return sorted;
}
private int function(int x, int a, int b, int c) {
return (a*x*x + b*x + c);
}
}