从薪资虚报被开除到LeetCode 1086：有序数组的转化与双指针解法

在网上看到一个帖子，有人吐槽自己的职场“滑铁卢”：为了争取更高薪资，面试时硬把不到一万的月薪说成了两万五，想冲击三万。结果公司真给了offer，却在入职后要求提交一年薪资流水。这下牛皮吹破了，回旋镖直接打在了自己身上。

想通过面试抬价的心情可以理解，打工人谁不想多挣点？但从一万吹到两万五，这就不是适度包装了，简直是给自己开了美颜十级滤镜。当然，公司这边操作也不算地道，真有疑虑就该在发offer前核实清楚，而不是等人入职了再掀桌子。

说到底，求职谈薪可以策略性上浮，但话不能太飘。否则最后工作没稳住，还得自己跑去仲裁，纯纯是给生活平白加了个困难副本。对于正在准备面试求职的朋友来说，这算是个生动的反面教材。

聊完八卦，进入正题。下面是一道与之画风迥异但值得琢磨的算法题：有序转化数组。

我第一次看到这题时，直觉思路很简单：先把数组里每个数都代入公式 f(x) = ax² + bx + c 计算，然后再整体排个序。

代码写起来不复杂，但题目特意给出了原数组有序这个条件，基本就是在提醒你：别把这个现成的优势浪费掉。

先看一个最直接、也最容易想到的Java写法：

public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
    int[] ans = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        ans[i] = calc(nums[i], a, b, c);
    }
    Arrays.sort(ans);
    return ans;
}

private int calc(int x, int a, int b, int c) {
    return a * x * x + b * x + c;
}

这么做能通过，但“味道”不太对。时间复杂度是 O(n log n)，而这道题其实可以做到 O(n)。

关键点不在公式计算本身，而在二次函数的图像特性上。

我们先看函数开口方向。
公式是：

f(x) = ax * x + b * x + c

如果 a > 0，抛物线开口向上，离对称轴越远，函数值越大。
如果 a < 0，抛物线开口向下，离对称轴越远，函数值越小。

而原数组 nums 本身已经是升序排列。
这时候就有一个很实用的判断：数组两端的元素，经过转化后往往会产生当前的最大值或最小值。

所以这题的做法，核心思路很像“有序数组平方”那道题，都是使用双指针。

为什么比较两端就能决定答案？
我们以 a > 0 为例。
抛物线开口向上，越靠近两端的输入 x，其函数值 f(x) 越大。所以，当前转化后序列的最大值，必然出现在 nums[left] 或 nums[right] 的转化结果中。

那么策略就可以是：

• 左右指针 left 和 right 分别指向数组两端。
• 比较两端值代入函数后的结果。
• 谁的值更大，谁就放到结果数组的当前末尾。
• 移动贡献了较大值的那个指针（left++ 或 right--）。

如果 a < 0 呢？
这时候开口向下，两端的输入 x 转化出的函数值反而更小。策略就反过来：把较小的值放到结果数组的当前开头。

想通了这一点，代码就顺理成章了：

public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] ans = new int[n];

        int left = 0;
        int right = n - 1;
        // 关键：根据开口方向决定填充起始位置
        int idx = a >= 0 ? n - 1 : 0;

        while (left <= right) {
            int lv = transform(nums[left], a, b, c);
            int rv = transform(nums[right], a, b, c);

            if (a >= 0) { // 开口向上，从后往前填充较大值
                if (lv > rv) {
                    ans[idx--] = lv;
                    left++;
                } else {
                    ans[idx--] = rv;
                    right--;
                }
            } else { // 开口向下，从前往后填充较小值
                if (lv < rv) {
                    ans[idx++] = lv;
                    left++;
                } else {
                    ans[idx++] = rv;
                    right--;
                }
            }
        }

        return ans;
    }

    private int transform(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}

我们拿一组数据走一遍流程。
例如：

nums = [-4, -2, 2, 4]
a = 1, b = 3, c = 5

函数是：

f(x) = x^2 + 3x + 5

先计算两端：

f(-4) = 9
f(4)  = 33

因为 a > 0，较大的 33 先放入结果数组末尾 ans[3]，right 指针左移。
接着比较 f(-4)=9 和 f(2)=15，15 更大，放入 ans[2]，left 指针右移（此时指向-2）。
依此类推，最终得到有序结果：

[3, 9, 15, 33]

整个过程没有额外的排序步骤，双指针只扫描了一遍数组。

这道题真正容易卡住的地方，不是双指针的比较，而是结果数组的填充方向。
很多人写到一半会混乱：

• a >= 0 时，结果需要从后往前填（因为先确定的是最大值）。
• a < 0 时，结果需要从前往后填（因为先确定的是最小值）。
  这个地方一旦弄反，结果要么是逆序的，要么就白优化了，还得再来一次排序。

还有一个细节，判断条件我写的是 a >= 0，而不是单纯的 a > 0。因为当 a == 0 时，函数退化成一次函数：

f(x) = bx + c

虽然此时不再是抛物线，但按上述逻辑（a>=0 分支）依然能正确处理，不需要单独拆分分支。

复杂度分析
优化后的复杂度非常清晰：

时间复杂度：O(n)
空间复杂度：O(n)

空间复杂度这里无法优化，因为题目要求返回一个新的数组。

这道题表面看是数学题，落到代码实现上，核心还是双指针技巧。题目中只要出现“原数组有序”这个条件，通常都值得先停下来思考一下，看看能不能避免那一次 O(n log n) 的排序。这一步想到了，题就做完了一半。更多有趣的算法技巧和讨论，欢迎来云栈社区交流分享。