LeetCode 360. 有序转化数组

2022-03-07 HGNULB 约 6 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 360. 有序转化数组

题意分析

给一个已按升序排列的整数数组 nums，以及二次函数的三个系数 a、b、c。把每个 nums[i] 代入 $f(x) = ax^2 + bx + c$，要求返回所有函数值组成的升序数组。

如果没有额外要求，把所有值算出来再排序即可，$O(n \log n)$ 结束。但题目的进阶明确要求 $O(n)$，这个信号排除了排序，逼我们去利用「输入已经有序」这个前提。

于是问题变成：一个升序序列经过 $f$ 映射后，值的排列有什么规律？ 这完全由 $f$ 的单调性决定，而二次函数的单调性只取决于开口方向和对称轴。

分三种情况。$a > 0$ 时抛物线开口向上，函数在对称轴左侧递减、右侧递增，所以对一个升序的自变量序列，函数值呈「先降后升」的 V 形——最大值必定出现在两端之一，最小值在中间某处。$a < 0$ 时开口向下，函数值呈「先升后降」的倒 V 形——最小值在两端之一，最大值在中间。$a = 0$ 时退化成一次函数 $bx + c$，全程单调，值序列要么整体升序（$b \ge 0$）要么整体降序（$b < 0$），可以看作 V 形和倒 V 形的退化特例。

「极值在两端」这个性质是全题的题眼：它意味着我们可以每次从两端各取一个候选、比较后确定当前的最值，然后把指针向中间收，这正是相向双指针的适用条件。

边界：数组可能只有一个元素；a、b、c 可以为负或为 0；nums 里可以有重复值；对称轴可能落在数组范围之外，此时函数在整个数组上单调，V 形退化成单边——好的实现应当让这些情况自然落入主逻辑而不需要特判。

解法：双指针收缩边界

核心思路

对有序自变量应用二次函数后，结果不是任意序列：a>0 时是单谷形，a<0 时是单峰形，a=0 时单调。因此任意尚未处理的连续区间，其函数值的最大值（开口向上）或最小值（开口向下）一定在两个端点之一。

使用左右指针保存未处理区间。若 a>=0，每轮取两端较大函数值，从结果末尾向前填；若 a<0，每轮取两端较小值，从结果开头向后填。a=0 的线性序列也满足端点最大值性质，可并入前一分支。

正确性说明：循环不变量是，[left,right] 恰好是未处理输入；结果已填部分有序且包含所有已取出的极值。端点比较得到当前剩余极值，放入对应结果端点后收缩一侧，故不变量继续成立。区间耗尽时结果全部填满并升序。

这种做法只利用端点极值，不需要计算对称轴，也不需要对变换结果重新排序。

解题步骤

初始化 left=0、right=n-1。

a>=0 时令写入位置从 n-1 向前移动；否则从 0 向后移动。

每轮计算左右端点的函数值。

按开口方向选择较大值或较小值，写入结果并移动对应指针。

当 left>right 时返回结果。

对 [-4,-2,2,4] 与 a=1,b=3,c=5，两端取最大并倒序填充，得到 [3,9,15,33]。若 a=-1，两端取最小并正序填充。单元素时 left==right 仍需执行一次，因此循环条件必须包含等号。

代码实现

class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int[] answer = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int write = a >= 0 ? nums.length - 1 : 0;

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

            if (a >= 0) {
                if (leftValue >= rightValue) {
                    answer[write--] = leftValue;
                    left++;
                } else {
                    answer[write--] = rightValue;
                    right--;
                }
            } else {
                if (leftValue <= rightValue) {
                    answer[write++] = leftValue;
                    left++;
                } else {
                    answer[write++] = rightValue;
                    right--;
                }
            }
        }
        return answer;
    }

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

func sortTransformedArray(nums []int, a int, b int, c int) []int {
	answer := make([]int, len(nums))
	left, right := 0, len(nums)-1
	write := 0
	if a >= 0 {
		write = len(nums) - 1
	}

	transform := func(x int) int {
		return a*x*x + b*x + c
	}

	for left <= right {
		leftValue := transform(nums[left])
		rightValue := transform(nums[right])

		if a >= 0 {
			if leftValue >= rightValue {
				answer[write] = leftValue
				left++
			} else {
				answer[write] = rightValue
				right--
			}
			write--
		} else {
			if leftValue <= rightValue {
				answer[write] = leftValue
				left++
			} else {
				answer[write] = rightValue
				right--
			}
			write++
		}
	}
	return answer
}

复杂度分析

时间复杂度： $O(n)$，每轮消耗一个输入元素。

空间复杂度： 不计返回数组为 $O(1)$。

关键点总结

二次函数在有序输入上形成单峰、单谷或单调序列，所需极值始终位于端点。

开口向上取最大值并从后向前填；开口向下取最小值并从前向后填。

a=0 仍满足端点最大值性质，可复用 a>=0 分支。

指针重合时还有一个元素未处理，循环条件必须是 left<=right。

易错点总结

取最大值却从结果开头填： 会得到降序结果。

所有 a 都按开口向上处理： a<0 时端点提供的是最小值。

循环写成 left<right： 会漏掉最后一个元素。

相等时不移动任何指针： 两端函数值相同时会死循环。

重新排序变换结果： 虽然正确，但退化为 $O(n\log n)$，没有利用输入有序性。

相似题目

题目	难度	考察点
977. 有序数组的平方	简单	本题在 $a=1, b=0, c=0$ 时的特例，值序列同为 V 形，是双指针骨架的最小载体
88. 合并两个有序数组	简单	同样从结果末尾倒着填以避免覆盖，练习「填充方向由取值方向决定」这一原则
4. 寻找两个正序数组的中位数	困难	有序性被用于二分划分而非线性收缩，对照理解何时该二分、何时该双指针
283. 移动零	简单	同向双指针的最简形式，用来区分「同向」与「相向」两种双指针的适用场景
167. 两数之和 II - 输入有序数组	简单	相向双指针靠单调性决定收缩哪一侧，与本题「极值在端点」是同一类推理
1200. 最小绝对差	简单	靠有序性把「任意两元素比较」降成「相邻比较」，同样是用有序性省掉一层枚举
462. 最小操作次数使数组元素相等 II	中等	有序数组上直接取中位数即得最优解，练习从函数形状反推最优位置