更新题目 排一个窗口求最大字典序
题目 amazon-max-shipment-order · 修改（rev 8） · · 2026-10-27 00:33
body
@@ -3,12 +3,12 @@ 这是 Amazon 自己编的题，套的是物流背景，没有对应的 LeetCode 原题【推断】。 -- 输入是一个数组 `shipmentOrder` 和一个整数 `windowSize`（下面记作 k）。`shipmentOrder` 的长度是 n，内容是 1 到 n 的一个排列（permutation），也就是这 n 个数每个恰好出现一次。 -- 你**必须恰好做一次**下面的操作：选一个起点 i，把从 i 开始、长度为 k 的连续窗口排成升序，窗口外的元素不动。题面的下标从 1 开始（1-based），所以起点的范围是 1 ≤ i ≤ n − k + 1。 -- 如果选到的窗口本来就是升序，排序后数组不变，这也算一次合法的操作；当动任何别的窗口都会让数组变小时，选这样的窗口就是最优解。 -- 要返回的是操作后能得到的、字典序（lexicographical order）最大的数组。比较两个等长数组的字典序时，从左往右找第一个不同的位置，这个位置上值大的那个数组更大。 -- 要实现的函数是 `maximizeShipmentOrder(shipmentOrder, windowSize)`，返回长度为 n 的数组 `int[n]`。 -- 数据范围是 1 ≤ windowSize ≤ n ≤ 2×10^5，并且保证 `shipmentOrder` 是 1..n 的排列。 +- 输入是数组 `shipmentOrder` 和整数 `windowSize`（下面记作 k）。`shipmentOrder` 的长度是 n，内容是 1 到 n 的一个排列（permutation），也就是这 n 个数每个恰好出现一次。 +- 你**必须恰好做一次**下面的操作：选一个起点 i，把从 i 开始、长度为 k 的连续窗口排成升序，窗口外的元素不动。题面下标从 1 开始，所以 $1 \le i \le n - k + 1$。 +- 选到的窗口本来就是升序时，排序后数组不变，这也算一次合法的操作。 +- 返回操作后能得到的、字典序（lexicographical order）最大的数组。比较两个等长数组的字典序时，从左往右找第一个不同的位置，这个位置上值大的那个数组更大。 +- 函数是 `maximizeShipmentOrder(shipmentOrder, windowSize)`，返回长度为 n 的 `int[n]`。 +- 数据范围是 $1 \le k \le n \le 2 \times 10^5$。 -原帖给的样例是 `shipmentOrder = [5, 1, 4, 3, 2]`、`windowSize = 3`，一共有三个可选的窗口： +原帖的样例是 `shipmentOrder = [5, 1, 4, 3, 2]`、k = 3，一共三个窗口可选： - i = 1，把 `[5,1,4]` 排序，得到 `[1,4,5,3,2]`。 @@ -16,34 +16,44 @@ - i = 3，把 `[4,3,2]` 排序，得到 `[5,1,2,3,4]`。 -第一个窗口的结果开头就变小了，比另外两个都小；后两个结果前两位相同，第三位上中间那个窗口的结果更大，所以答案是 `[5, 1, 3, 4, 2]`。 - -**另一篇面经的描述。** 另一篇面经的楼主没贴题面，只描述了规则和输入输出：给一个包裹列表和一个 window size，只能对窗口里的包裹排序，返回最佳的、排好序的新列表。规则（只能排序窗口里的元素）和输入输出（包裹列表加窗口大小，返回新列表）都和本题一致，所以这篇说的就是本题，是楼主自己描述了题目，不是推断出来的。楼主没说「最佳」指的是字典序最大，也没说只排一次，这两点以上面的完整题面为准；两人做 OA 的时间也相近（见「面经里怎么考的」）。 +第一个结果开头就变小了，比另外两个都小。后两个结果前两位相同，第三位上 3 比 2 大，所以答案是 `[5, 1, 3, 4, 2]`。 ## 面经里怎么考的 -- **2026-10 初，一位应届生**（软件工程类本科全职岗）的 OA 是一道编程题加一道 AI Debug 题，编程题就是这题。楼主贴了完整的题面、约束和样例，但没写自己的解法、有没有通过全部测试（AC），也没写限时。另一道 AI Debug 题（AI 辅助调试）给的是一个类似 Jira（任务跟踪工具）的项目，bug 出在创建 Issue 和 sub-issue 的地方，详见 [[q:amazon-oa-ai-debug]]。 -- **2026-09 底，一位在职跳槽的楼主**（软件工程类硕士全职岗）的 OA 第一题限时 40 分钟。楼主没贴题面，但描述的规则（只能对窗口里的包裹排序）和输入输出（包裹列表加 window size，返回排好序的新列表）都和本题一致，所以就是这题，详见「题目」最后一段。楼主说这是「比较难的 DP 题」，觉得现场能做出来的人都很厉害；楼主之前见过原题，所以做得还算顺，但想不起在哪见过（可能是某个讨论里有人贴过）。第二题是 60 分钟的 AI 辅助编程，是一道经典的 OOP（面向对象）题：题目本身不难，但一共 6 个测试，每个测试都有不少问题要解决，时间偏紧，AI 基本没帮上忙，最后过了 5 个，第 6 个没来得及看。AI 题用的编程语言和楼主选的一致（楼主选了 C++，AI 题也是 C++）。 +- **2026-10 初，一位应届生**（软件工程类本科全职岗）的 OA 是一道编程题加一道 AI Debug 题，编程题就是这题。楼主贴了完整的题面、约束和样例，没写自己的解法、有没有通过全部测试，也没写限时。另一道 AI Debug 题（AI 辅助调试）给的是一个类似 Jira 的项目，bug 出在创建 Issue 和 sub-issue 的地方，见 [[q:amazon-oa-ai-debug]]。 +- **2026-09 底，一位在职跳槽的楼主**（软件工程类硕士全职岗）的 OA 第一题限时 40 分钟。楼主没贴题面，只描述了规则和输入输出：给一个包裹列表和一个 window size，只能对窗口里的包裹排序，返回最佳的、排好序的新列表。规则和输入输出都和上面的题面一致，所以是同一题。楼主没说「最佳」是字典序最大，也没说只排一次，这两点以完整题面为准。楼主说这是「比较难的 DP 题」，觉得现场能做出来的人都很厉害。楼主之前见过原题，所以做得还算顺，但想不起在哪见过（可能是某个讨论里有人贴过）。第二题是 60 分钟的 AI 辅助编程，一道经典的 OOP 题，6 个测试过了 5 个，AI 基本没帮上忙，用的语言和楼主选的一致（C++）。 -**教训是别被「DP」这个说法带偏。** 楼主把它叫作 DP 题，评论区也有人猜是 0/1 背包（0/1 knapsack，一道经典的 DP 题），可见这题很容易被当成 DP，但它其实**用不着 DP**。核心是一个贪心（greedy）的观察：每个窗口排序后都只会让数组变小或不变，而结果的好坏取决于从哪个位置开始变小，所以只要选「第一个被改动的位置」尽量靠后的窗口（理由见「思路」）。每个窗口的这个位置可以用区间最小值查询（range minimum query）或单调栈（monotonic stack）求出来，总共 O(n log n) 就够了。 +这题容易被当成 DP：楼主这么叫，评论区也有人猜是 0/1 背包。它其实**用不着 DP**，位置之间没有需要从小问题推到大问题的子问题。结果好坏由「第一个被改动的位置」决定，贪心地比较每个窗口的这个位置就够了（见「思路」），总共 $O(n \log n)$。 -**也别写暴力。** 暴力做法是对每个窗口都排一次序、拼出整个数组再比较，合计 O((n − k + 1)·(n + k log k))：只要 k 不接近 n，这就是 n² 量级，n = 2×10^5 时会超时。 +也别交暴力解。对每个窗口都排一次序、拼出整个数组再比较，合计 $O((n - k + 1)(n + k \log k))$，只要 k 不接近 n 就是 $n^2$ 量级。2026-10-27 实测（随机排列，k = 2），Python 暴力解在 $n = 10^4$ 时要 0.86 秒，$n = 2 \times 10^4$ 时要 4.73 秒，按平方外推到 $n = 2 \times 10^5$ 约 470 秒。 -考到这题的两篇面经都只写了「1 道编程 + 1 道 AI 题」，都没提 Work Simulation（Amazon OA 里的一个非编程部分，在模拟的工作场景里做选择题）。在职那篇的编程题限时 40 分钟（应届那篇没写限时），读题、想清楚贪心思路、写代码、自己测试都得在这个时间里做完，所以最好考前就把下面两种写法之一练熟。 +两篇面经都只写了一道编程题加一道 AI 题，都没提编程之后的 Work Simulation（见 [[q:amazon-oa-work-simulation]]）。在职那篇限时 40 分钟，读题、想清楚贪心、写代码、自测都在这段时间里，最好考前就把下面的写法练熟。 ## 思路 -楼主没给解法，下面的思路是自己推导的。为了确认推导没错，已经用对拍验证过：另写一个简单但肯定正确的暴力解，在小数据上（穷举所有输入，或者随机生成）同时跑暴力解和正式解，把两边的输出逐一比较，这种做法叫对拍。暴力解和对拍的范围见「代码」。 +楼主没给解法，下面是自己推导的，并用暴力解对拍验证过（见「代码」）。下面用 i 表示窗口起点，用 $f(i)$ 表示窗口 i 排序后第一个发生变化的位置，代码里分别是 `start` 和 `first_change`，下标从 0 开始。 -1. **排升序只会让数组变小或不变。** 看窗口里第一个和排序结果不同的位置：在它之前，窗口里的数都没动；排序后这个位置放的是窗口里从这里往后那些数的最小值，而原来那个数和它不同，只能比它大。所以结果在这个位置上变小了，前面又都没变，按字典序整个数组也就变小了。换句话说，原数组是所有可能结果的上界（upper bound），任何一次操作都得不到比它更大的数组。 -2. **只要有一个窗口本来就是升序，答案就是原数组。** 排这个窗口不改变数组，而上一步说明不可能得到比原数组更大的结果。有没有这样的窗口，等价于原序列里有没有长度 ≥ k 的连续递增段；k = 1 时每个窗口只有一个数，一定成立。 -3. **否则每个窗口 i 排序后都会让数组变小。** 把变小开始的位置，也就是窗口 i 排序后第一个发生变化的位置，记作 `f(i)`。`f(i)` 越靠后，结果越大：设 f(i) < f(j)，两种结果在 f(i) 之前都等于原数组；到了 f(i) 这个位置，窗口 i 的结果已经变小了，窗口 j 的结果还等于原值，所以窗口 j 的结果更大。因此要**最大化 f(i)**，也就是找第一个变化位置最靠后的窗口。 -4. **怎么算 f(i)。** 下面有两种写法，时间复杂度一样，各自的取舍见「代码」和「复杂度」。 - - 写法一用二分查找（binary search）加稀疏表（sparse table）。设 t 为窗口开头连续「已经在排序后该在的位置上」的元素个数，那么第一个变化的位置就是 f(i) = i + t。窗口开头的 t 个数都已经就位，当且仅当这 t 个数递增，并且第 t 个比窗口里剩下的数都小。这个条件有单调性：t 成立，t − 1 也一定成立，所以可以二分找出最大的 t。二分的每一步要查「窗口里剩下那一段的最小值」，这是一次区间最小值查询，用稀疏表可以 O(1) 回答。稀疏表的做法是预先算好从每个位置开始、长度为二的幂的区间的最小值；查任意区间时，找两段互相重叠、合起来正好覆盖它的这种区间，取两者的较小值。 - - 写法二用单调栈（monotonic stack）加小根堆（min-heap，堆顶总是最小元素的堆）。记 `nse[p]` 为位置 p 右边第一个比它小的数所在的位置，这叫「下一个更小元素」（next smaller element）。所有位置的 `nse` 可以用单调栈一趟扫描求出：栈里存位置，对应的值从栈底到栈顶递增；扫到一个新数时，栈顶的值比它大就弹出，被弹出的位置的 `nse` 就是当前位置。有了 `nse`，f(i) 就是窗口里最靠左的、在窗口内右边还有更小数的位置，即窗口里最靠左的满足 `nse[p] ≤ i + k − 1` 的位置 p。为什么是它：这个位置左边的每个数，在窗口里往后都没有更小的数，所以它们是递增的，并且比后面所有数都小，已经在排序后该在的位置上；而这个位置自己后面有更小的数，排序后这里会换成一个更小的值。实现时，窗口右端每右移一格，就把 `nse` 等于新右端的那些位置放进小根堆（堆里存的是位置，所以堆顶就是最靠左的位置），再把堆顶上已经落到窗口左端之外（< i）的位置弹掉，剩下的堆顶就是 f(i)。如果堆空了，说明窗口里没有逆序（前面的数比后面的数大），窗口本来就是升序，回到第 2 步的情况。 -5. **f 相同时取更靠左的窗口。** 设 i < j，f(i) = f(j) = p。两种结果在 p 之前一样（都等于原数组），在 j + k − 1 之后也一样（两个窗口都碰不到那里）。中间从 p 到 j + k − 1 这一段，两边用的是同一组数：窗口 j 的结果把这组数排成了升序，这是这组数字典序最小的排法；窗口 i 的结果是同一组数的另一种排法（落在窗口 i 里的前一段是升序，后面保持原样）。字典序最小的排法不会比任何别的排法大，所以 i 不会比 j 差。 +1. **排升序只会让数组变小或不变。** 看窗口里第一个和排序结果不同的位置。在它之前，窗口里的数都没动。排序后这个位置放的是窗口里从这里往后那些数的最小值，原来那个数和它不同，只能比它大。所以结果在这个位置上变小了，前面又都没变，整个数组按字典序也就变小了。由此可见，原数组比任何一次操作的结果都不小。如果允许不操作，答案永远是原数组，这也是题面要求恰好排一次的原因。 +2. **有一个窗口本来就是升序，答案就是原数组。** 排这个窗口不改变数组，而第 1 步说明不可能得到比原数组更大的结果。k = 1 时每个窗口只有一个数，一定成立。 +3. **否则每个窗口排序后都会让数组变小，要找 $f(i)$ 最大的窗口。** 设 $f(i) < f(j)$。两个结果在 $f(i)$ 之前都等于原数组。到了位置 $f(i)$，窗口 i 的结果已经变小，窗口 j 的结果还等于原值，所以窗口 j 的结果更大。 + +> [!say] Sorting a window ascending can never make the array larger: at the first position it changes, the value goes down. So if some window is already sorted, the original array is the answer. Otherwise I want the window whose first change happens as late as possible, and I break ties by taking the leftmost window. + +4. **$f(i)$ 是窗口里最靠左的、在窗口内右边还有更小数的位置。** 这个位置左边的每个数，在窗口里往后都没有更小的数，所以它们递增，并且比后面所有数都小，已经在排序后该在的位置上。而这个位置自己后面有更小的数，排序后这里会换成一个更小的值。这个判断只对最靠左的那一个位置成立：窗口 `[4,2,1,3]` 里的 2 右边有 1，可排成 `[1,2,3,4]` 后这一位还是 2。 + - 要快速判断「右边有没有更小的数」，先求「下一个更小元素」（next smaller element）：`nse[p]` 是位置 p 右边第一个比它小的数所在的位置，没有就记为 n。用单调栈（monotonic stack）扫一趟就能求出全部 `nse`。于是位置 p 在窗口 $[i, i + k - 1]$ 里算数，当且仅当 $p \ge i$ 并且 `nse[p]` $\le i + k - 1$。 + - 窗口从左往右滑，右端每到一个新位置 r，就把 `nse[p] == r` 的那些 p 放进一个按位置排的小根堆（min-heap），再把堆顶上已经滑出左端（小于 i）的位置弹掉。剩下的堆顶就是 $f(i)$。堆空了说明窗口里没有逆序（前面的数比后面的数大），窗口本来就是升序，回到第 2 步。 + +> [!say] For each window, the first changed position is the leftmost index that has a smaller element later inside the window. I precompute the next smaller element with a monotonic stack, slide the window, and keep candidate indices in a min-heap, which gives O(n log n) overall. + +5. **$f$ 相同时取更靠左的窗口。** 设 $i < j$ 且 $f(i) = f(j) = p$。因为 $p = f(j) \ge j$，从 p 到 $j + k - 1$ 这一段整个落在窗口 j 里。两个结果在 p 之前一样（都等于原数组），在 $j + k - 1$ 之后也一样（两个窗口都碰不到）。中间这一段两边用的是同一组数：窗口 i 的结果在 i 到 $p - 1$ 上没动，所以 p 到 $i + k - 1$ 上放的还是原来这些位置的数，$i + k$ 到 $j + k - 1$ 在窗口 i 外面，也没动。窗口 j 的结果把这组数排成了升序，这是这组数字典序最小的排法。窗口 i 的结果只是同一组数的某一种排法，不会比升序小，所以窗口 i 不比窗口 j 差。 + +求 $f(i)$ 还有一种写法，用二分查找（binary search）加区间最小值查询（range minimum query）。设 t 是窗口开头已经在排序后位置上的数的个数，那么 $f(i) = i + t$。开头 t 个数都就位，当且仅当这 t 个数递增，并且第 t 个数比窗口里剩下的数都小。 + +- 先用从 i 开始的严格递增段长度给 t 封顶，在封顶范围内，「第 t 个数比剩下的都小」这个条件有单调性：设它对 t 成立。前 t 个数递增，第 $t - 1$ 个数比第 t 个小，第 t 个又比后面的都小，所以第 $t - 1$ 个也比它后面的都小，条件对 $t - 1$ 也成立。于是可以二分出最大的 t。 +- 封顶不能省。窗口 `[3,1,2,4]` 里，这个条件在 t = 2、3 时成立（1 < 2、2 < 4），在 t = 1 时不成立（3 不小于 1），没有单调性。这里递增段只有 `[3]`，长度 1，封顶后 t 只能取 0 或 1，二分得到 t = 0。 +- 二分每一步要查「窗口里剩下那一段的最小值」。稀疏表（sparse table）预先算好从每个位置开始、长度为 2 的幂的区间的最小值，查任意区间时取两段互相重叠、合起来正好盖住它的区间，较小的那个就是答案，一次 $O(1)$。 + +这种写法复杂度同样是 $O(n \log n)$，但要多建一张表、多一层二分，下标更容易写错，考场上推荐单调栈加堆的写法。2026-10-27 用这种写法的一份实现（这里不贴代码）跑了「代码」一节里同一组穷举对拍，40319 组全部和暴力解一致。 ## 代码 - -已运行（Python 3）。下面这段代码原样跑过：原帖样例和几个边界用例全部通过；另外和后面的暴力解做了对拍，范围是穷举 n ≤ 7 的全部排列和全部 k，另加随机数据，两种写法的结果都和暴力解一致。考场上更推荐写法二：它不用二分，要小心的边界情况少，限时下更不容易写错下标；常数因子也更小（同样是 O(n log n)，实际执行的操作更少），实测比写法一快，见「复杂度」。 ```python @@ -51,76 +61,49 @@ -# 写法一：稀疏表区间最小值 + 每个窗口二分 t +def next_smaller_index(order): + """nse[p] 是 p 右边第一个比 order[p] 小的下标，没有就是 len(order)。""" + n = len(order) + nse = [n] * n + stack = [] # 存下标，对应的值从栈底到栈顶递增 + for p, value in enumerate(order): + while stack and order[stack[-1]] > value: + nse[stack.pop()] = p + stack.append(p) + return nse + + def maximize_shipment_order(order, k): n = len(order) - run = [1] * n # run[i]: 从 i 开始的严格递增段长度 - for i in range(n - 2, -1, -1): - if order[i] < order[i + 1]: - run[i] = run[i + 1] + 1 + nse = next_smaller_index(order) + positions_by_nse = [[] for _ in range(n + 1)] + for p in range(n): + positions_by_nse[nse[p]].append(p) - sp = [order[:]] # 稀疏表，查区间最小值 - j = 1 - while (1 << j) <= n: - prev, half = sp[-1], 1 << (j - 1) - sp.append([min(prev[x], prev[x + half]) for x in range(n - (1 << j) + 1)]) - j += 1 + # 小根堆里放「右边那个更小的数已经进了窗口」的下标 + heap = [] + for right in range(k - 1): # 第一个窗口里、右端之前的部分 + for p in positions_by_nse[right]: + heapq.heappush(heap, p) - def range_min(l, r): # 闭区间，l <= r - b = (r - l + 1).bit_length() - 1 - return min(sp[b][l], sp[b][r - (1 << b) + 1]) - - best_f, best_i = -1, 0 - for i in range(n - k + 1): - hi = min(run[i], k) - if hi == k: - return order[:] # 这个窗口本来就是升序，原序列最大 - lo_t, hi_t = 0, hi - while lo_t < hi_t: - mid = (lo_t + hi_t + 1) // 2 - if order[i + mid - 1] < range_min(i + mid, i + k - 1): - lo_t = mid - else: - hi_t = mid - 1 - if i + lo_t > best_f: # 严格大于才换：并列取最左 - best_f, best_i = i + lo_t, i - res = order[:] - res[best_i:best_i + k] = sorted(res[best_i:best_i + k]) - return res - - -# 写法二：下一个更小元素（单调栈）+ 小根堆，代码更短、常数更小 -def maximize_shipment_order_heap(order, k): - n = len(order) - nse = [n] * n # nse[p]: p 右边第一个比 order[p] 小的位置，没有就是 n - stack = [] - for p in range(n): - while stack and order[stack[-1]] > order[p]: - nse[stack.pop()] = p - stack.append(p) - by_nse = [[] for _ in range(n + 1)] - for p in range(n): - by_nse[nse[p]].append(p) - - heap = [] # 已知「在窗口右端以内有更小元素」的位置 - for r in range(k - 1): - for p in by_nse[r]: + best_first_change, best_start = -1, 0 + for start in range(n - k + 1): + right = start + k - 1 + for p in positions_by_nse[right]: heapq.heappush(heap, p) - best_f, best_i = -1, 0 - for i in range(n - k + 1): - for p in by_nse[i + k - 1]: # 右端扩到 i+k-1 - heapq.heappush(heap, p) - while heap and heap[0] < i: # 左端之外的扔掉 + while heap and heap[0] < start: # 已经滑出窗口左端 heapq.heappop(heap) if not heap: - return order[:] # 窗口里没有逆序，本来就是升序 - if heap[0] > best_f: # 严格大于才换：并列取最左 - best_f, best_i = heap[0], i - res = order[:] - res[best_i:best_i + k] = sorted(res[best_i:best_i + k]) - return res + return order[:] # 窗口本来就是升序，原数组就是答案 + first_change = heap[0] + if first_change > best_first_change: # 严格大于：并列时留最左的窗口 + best_first_change, best_start = first_change, start + + result = order[:] + result[best_start:best_start + k] = sorted(result[best_start:best_start + k]) + return result def maximizeShipmentOrder(shipmentOrder, windowSize): # OA 里的函数名 - return maximize_shipment_order_heap(shipmentOrder, windowSize) + return maximize_shipment_order(shipmentOrder, windowSize) @@ -128,19 +111,16 @@ tests = [ ([5, 1, 4, 3, 2], 3, [5, 1, 3, 4, 2]), # 原帖样例 - ([3, 2, 1], 2, [3, 1, 2]), - ([3, 1, 2], 2, [3, 1, 2]), - ([2, 4, 3, 1], 3, [2, 3, 4, 1]), - ([5, 4, 3, 2, 1], 2, [5, 4, 3, 1, 2]), - ([4, 3, 2, 1], 4, [1, 2, 3, 4]), - ([2, 1], 1, [2, 1]), + ([3, 1, 2], 2, [3, 1, 2]), # 有现成的升序窗口 + ([2, 4, 3, 1], 3, [2, 3, 4, 1]), # 两个窗口并列，取左边 + ([5, 4, 3, 2, 1], 2, [5, 4, 3, 1, 2]), # 整段递减 + ([4, 3, 2, 1], 4, [1, 2, 3, 4]), # k = n + ([2, 1], 1, [2, 1]), # k = 1 ] - for a, k, exp in tests: - assert maximize_shipment_order(a, k) == exp - assert maximize_shipment_order_heap(a, k) == exp - assert maximizeShipmentOrder(a, k) == exp + for order, k, expected in tests: + assert maximizeShipmentOrder(order, k) == expected, (order, k) print("ok") ``` -下面是对拍用的暴力解。它枚举每一个窗口，排序后拼出整个数组，直接取字典序最大的那个。这样写简单、不容易错，适合当标准答案，但太慢，不能直接交（原因见「易错点」最后一条）。 +对拍用的暴力解枚举每个窗口，排序后拼出整个数组，直接取最大的。它简单、不容易错，适合当标准答案，但太慢，不能交： ```python @@ -154,43 +134,17 @@ ``` +2026-10-27 用 Python 3.13.17 跑过上面两段代码，结果如下。 + +- 正解的 6 个用例全部通过，输出 `ok`。 +- 和暴力解对拍：穷举 $n \le 7$ 的全部排列和全部 k，共 40319 组，全部一致。另外 3000 组随机数据（$n \le 60$）也全部一致。 +- $n = 2 \times 10^5$ 时，输入取随机排列和整段递减两种，k 取 1、2、1000、$10^5$、n，正解每次用时 0.13 到 0.36 秒。 + ## 复杂度 -- 写法一的时间复杂度是 O(n log n)：建稀疏表要 O(n log n)；之后每个窗口做一次二分，二分的每一步用稀疏表 O(1) 查一次最小值。空间是 O(n log n)，用在稀疏表上。 -- 写法二的时间复杂度也是 O(n log n)：用单调栈求 `nse` 是 O(n)，每个位置最多进堆一次、出堆一次，每次堆操作是 O(log n)。空间是 O(n)。 -- 两种写法最后都要把选中的窗口排一次序，这一步是 O(k log k)；因为 k ≤ n，不影响总的量级。 -- 在本机用 Python 实测 n = 2×10^5 的情况（输入取随机排列和整段递减两种，k 在 1 到 n 之间取了几档）：写法一大约 0.5–1 s，写法二大约 0.1–0.3 s，具体因机器而异。 +时间 $O(n \log n)$。单调栈求 `nse` 是 $O(n)$。每个位置最多进堆一次、出堆一次，每次堆操作 $O(\log n)$。最后排一次选中的窗口是 $O(k \log k)$，不超过前面的量级。空间 $O(n)$，用在 `nse`、按 `nse` 分组的列表和堆上。 ## 易错点 -- **并列时必须取最左边的窗口**，所以更新条件用 `>`，不能用 `>=`：用 `>=` 的话，后面 f 相同的窗口会把前面的覆盖掉。例如 `[2,4,3,1]`、k = 3，两个窗口的 f 都是第 2 个位置；取左边的窗口得到 `[2,3,4,1]`（对），取右边的得到 `[2,1,3,4]`（错）。如果把 `>` 写成了 `>=`，对拍能抓出来，比如 `[1,4,2,3]`、k = 3 这组数据就会出错。 -- **「恰好一次」不等于「必须改变数组」。** 只要有一个窗口本来就是升序，排它不改变数组，就直接返回原数组；k = 1 时每个窗口都只有一个数，一定原样返回。 -- **注意下标换算。** 题面的下标从 1 开始（1-based），代码里从 0 开始（0-based），所以代码里起点的范围是 `0..n-k`。 -- **写法一里的二分不会查到空区间。** 代码先判断 `run[i] ≥ k`，成立就直接返回；所以走到二分时 t 最多是 k − 1，`range_min(i+t, i+k-1)` 查的区间不会是空的。 -- 写法二要在循环开始前，先把 `nse` 落在 `0..k-2` 的位置放进堆里。堆里应该放的是「右边那个更小的数已经进入窗口」的位置。循环里每一步只补 `nse == i+k-1` 的那一批，也就是更小的数恰好是刚进入窗口的新右端的那些位置；而第一个窗口一开始就包含了右端之前的那些位置，`nse` 落在那里的位置在循环里不会被补到，所以要提前放进去。`nse == n` 表示右边没有更小的数，这样的位置永远不入堆。 -- 写法二只能用「最靠左」的那一个位置。对窗口里别的位置来说，「右边有更小的数」和「排序后会被改动」并不等价。例如窗口 `[4,2,1,3]` 里的 2 右边有 1，但排成 `[1,2,3,4]` 后这一位还是 2。 -- **别暴力枚举。** 对每个窗口都排序、再拼出整个数组比较，合计 O((n − k + 1)·(n + k log k))；只要 k 不接近 n，这就是 n² 量级，n = 2×10^5 时会超时。 - -## 测试用例 - -- `[5,1,4,3,2]`、k = 3 → `[5,1,3,4,2]`（原帖样例） -- `[3,2,1]`、k = 2 → `[3,1,2]` -- `[3,1,2]`、k = 2 → `[3,1,2]`（窗口 `[1,2]` 本来就是升序，数组不变） -- `[2,4,3,1]`、k = 3 → `[2,3,4,1]`（两个窗口的 f 相同，取最左的窗口） -- `[5,4,3,2,1]`、k = 2 → `[5,4,3,1,2]`（整个数组递减时，每个窗口都在自己的第一位就变小，最后一个窗口第一个变化的位置最靠后，所以排最后两个数最好） -- `[4,3,2,1]`、k = 4 → `[1,2,3,4]`（k = n，只能整体排序） -- `[2,1]`、k = 1 → `[2,1]`（k = 1，一定不变） -- `[1,2,3,4]`、k = 2 → `[1,2,3,4]`（本来就是升序） - -## Follow-up - -- **如果允许不操作**，答案永远是原数组，因为第 1 步已经说明排升序只会让数组变小或不变。这也解释了为什么题面要求恰好排一次：否则答案总是原数组，题目就没什么可做的了。 -- **如果有重复值（不再是排列）**，写法二可以直接用，因为 `nse` 找的是严格更小的数，后面只有相等的数时，这个位置排序后不会变。写法一要把 `run` 和二分里的 `<` 改成 `<=`，因为和后面相等的数也已经在排序后该在的位置上。写法二原样、写法一改完之后，都在带重复值的随机数据上和暴力解对拍过。 -- **如果面试官问为什么不用 DP**，可以这样回答：DP 适用于有重叠子问题（overlapping subproblems）和最优子结构（optimal substructure）、能靠状态转移（state transition）从小问题推出大问题的情况，而这题的位置之间没有需要转移的子问题。结果的字典序大小主要由第一个变化的位置决定，f 相同时再取最左的窗口，所以直接贪心地比较每个窗口的 f(i) 就够了。 - -## 英文讲法 - -面试时可以分两段讲：先讲关键观察，再讲实现。 - -> [!say] Sorting a window ascending can never make the array larger: at the first position it changes, the value goes down. So if some window is already sorted, the original array is the answer. Otherwise I want the window whose first change happens as late as possible, and I break ties by taking the leftmost window. - -> [!say] For each window, the first changed position is the leftmost index that has a smaller element later inside the window. I precompute the next smaller element with a monotonic stack, slide the window, and keep candidate indices in a min-heap, which gives O(n log n) overall. +- **并列时必须留最左边的窗口**，更新条件用 `>`，不能用 `>=`（「思路」第 5 步）。改成 `>=` 后，`[2,4,3,1]`、k = 3 会返回 `[2,1,3,4]`，正确答案是 `[2,3,4,1]`。同一组穷举数据里，`>=` 的版本错了 2893 组（2026-10-27 实测）。 +- **循环之前要先把 `nse` 落在 `0..k-2` 的位置放进堆。** 循环里每一步只补 `nse` 等于新右端的那一批，第一个窗口里更早进来的那些更小的数不会被补到。漏掉这一段，`[2,1,4,3]`、k = 3 会把第一个窗口当成升序，直接返回原数组 `[2,1,4,3]`，可两个窗口都不是升序，这个结果根本得不到，正确答案是 `[2,1,3,4]`。同一组穷举数据里，漏掉预先入堆的版本错了 15767 组（2026-10-27 实测）。 +- **「恰好一次」不等于「必须改变数组」**（「思路」第 2 步）。有一个窗口本来就是升序，就直接返回原数组，k = 1 时一定原样返回。
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-2313", + "rewritten_at": "2026-10-27" +}