更新题目 2771. Longest Non-decreasing Subarray From Two Arrays

题目 lc2771 · 修改（rev 2） · cc · 2026-10-26 23:11
body

@@ -1,5 +1,13 @@
 ## 题目
 
-两个等长数组 nums1、nums2。构造 nums3：每个位置从 nums1[i] 或 nums2[i] 里选一个。求 nums3 里最长的非递减连续子数组的长度的最大可能值。
+给两个长度都是 `n` 的整数数组 `nums1`、`nums2`。构造一个新数组 `nums3`：每个下标 `i` 上，`nums3[i]` 从 `nums1[i]` 和 `nums2[i]` 里任选一个。求 `nums3` 里最长的非递减连续子数组的长度，在所有选法里最大能是多少。函数返回一个整数。
+
+非递减指每个数都不小于前一个数，相等也算。LeetCode 的范围是 `1 <= n <= 10^5`，`1 <= nums1[i], nums2[i] <= 10^9`。
+
+| `nums1` | `nums2` | 输出 | 怎么选 |
+| --- | --- | --- | --- |
+| `[2, 3, 1]` | `[1, 2, 1]` | `2` | 选成 `[2, 2, 1]`，前两个非递减 |
+| `[1, 3, 2, 1]` | `[2, 2, 3, 4]` | `4` | 选成 `[1, 2, 3, 4]`，整个数组非递减 |
+| `[1, 1]` | `[2, 2]` | `2` | 选成 `[1, 2]` 或 `[1, 1]` |
 
 [LeetCode 原题](https://leetcode.com/problems/longest-non-decreasing-subarray-from-two-arrays/)
@@ -7,32 +15,73 @@
 ## 面经里怎么考的
 
-Visa 26NG 的 HackerRank OA 第三题（2026-04，楼主挂了）：楼主写的题面和这题一致（每个下标从 A 或 B 选一个，求最长的连续非递减段），没写题号。同一场第一题是 [[q:visa-double-b-max-min-sum]]。
+Visa 26NG 的 HackerRank OA 第三题（2026-04，楼主挂了）：楼主写的题面和这题一致（每个下标从 A 或 B 选一个，求最长的连续非递减段），没写题号，对应到 2771 是【推断】。同一场第一题是 [[q:visa-double-b-max-min-sum]]。下面按 LeetCode 原题写。
 
 ## 思路
 
-状态 DP：`d1` 表示「以位置 i 结尾、位置 i 选 nums1[i]」时的最长长度，`d2` 是选 nums2[i] 的。位置 i 选值 v 时，能接在前一个位置的哪个选择后面，取决于 v 是否不小于它；接不上就从 1 重新开始。
+用两个状态做 DP，按下标从左往右推：
+
+- `end_on_1`：以下标 `i` 结尾、并且下标 `i` 选了 `nums1[i]` 的非递减段，最长有多长。
+- `end_on_2`：同样以下标 `i` 结尾，下标 `i` 选的是 `nums2[i]`。
+
+两个状态就够用。一段以下标 `i` 结尾的段能不能接上下一个数，只看它的最后一个值，而最后一个值只有 `nums1[i]`、`nums2[i]` 两种，所以每种最后一个值只记最长的那一段。
+
+转移：下标 `i` 选值 `v` 时，`v >= nums1[i - 1]` 就能接在 `end_on_1` 那段后面，长度是 `end_on_1 + 1`。`v >= nums2[i - 1]` 就能接在 `end_on_2` 那段后面，长度是 `end_on_2 + 1`。两边都接不上，就从 `v` 自己开始，长度为 1。三者取最大。答案是扫描过程中所有 `end_on_1`、`end_on_2` 的最大值。
+
+> [!say] I keep two running lengths, one for ending on nums1[i] and one for ending on nums2[i], and each new value extends whichever previous choice it doesn't go below.
 
 ## 代码
 
 ```python
-def max_non_decreasing_length(nums1, nums2):
-    best = d1 = d2 = 1
+from typing import List
+
+
+def max_non_decreasing_length(nums1: List[int], nums2: List[int]) -> int:
+    """Longest non-decreasing subarray of nums3, where nums3[i] is nums1[i] or nums2[i]."""
+    if len(nums1) != len(nums2):
+        raise ValueError("nums1 and nums2 must have the same length")
+    if not nums1:
+        return 0
+
+    best = 1
+    end_on_1 = end_on_2 = 1  # longest run ending at i that picks nums1[i] / nums2[i]
     for i in range(1, len(nums1)):
-        a, b = nums1[i], nums2[i]
-        p1, p2 = nums1[i - 1], nums2[i - 1]
-        n1 = max(d1 + 1 if a >= p1 else 1, d2 + 1 if a >= p2 else 1)
-        n2 = max(d1 + 1 if b >= p1 else 1, d2 + 1 if b >= p2 else 1)
-        d1, d2 = n1, n2
-        best = max(best, d1, d2)
+        prev1, prev2 = nums1[i - 1], nums2[i - 1]
+        cur1, cur2 = nums1[i], nums2[i]
+        end_on_1, end_on_2 = (
+            longest_run_ending_with(cur1, prev1, prev2, end_on_1, end_on_2),
+            longest_run_ending_with(cur2, prev1, prev2, end_on_1, end_on_2),
+        )
+        best = max(best, end_on_1, end_on_2)
     return best
+
+
+def longest_run_ending_with(value: int, prev1: int, prev2: int, end_on_1: int, end_on_2: int) -> int:
+    """Longest run ending with `value`, given the two runs ending at the previous index."""
+    length = 1
+    if value >= prev1:
+        length = max(length, end_on_1 + 1)
+    if value >= prev2:
+        length = max(length, end_on_2 + 1)
+    return length
 ```
 
-本机跑过官方例子。
+招聘方说代码写法也计分，这一版有两处考虑：
+
+- 转移拆成 `longest_run_ending_with`，两个新状态用同一个函数算，主循环里不出现两行几乎一样的长表达式。两个新值放在一条语句里同时赋值，原因见「易错点」第三条。
+- 两个数组长度不同时抛 `ValueError`。LeetCode 保证 `n >= 1`，HackerRank 的题面不一定写，空数组里没有子数组，这里返回 0。
+
+2026-10-26 用 Python 3.13 实际跑过：
+
+- 三个例子分别得 2、4、2。空数组返回 0，长度不同抛 `ValueError`。
+- 和暴力解对拍（暴力解枚举全部 `2^n` 种选法）。长度 1 到 5、每个数 0 到 3 的全部 1,118,480 对数组，加上 3000 组长度不超过 10 的随机数组，结果全部一致。
+- `n = 10^5` 时，随机数组耗时 28 毫秒，两个数组都是 `1, 2, …, 10^5` 时返回 `10^5`，耗时 35 毫秒。
 
 ## 复杂度
 
-O(n) 时间，O(1) 空间。
+时间 `O(n)`，扫一遍，每个下标做常数次比较。额外空间 `O(1)`，只存两个状态和当前最大值。
 
-## 英文讲法
+## 易错点
 
-> [!say] I keep two running lengths, one for ending on nums1[i] and one for ending on nums2[i], and each new value extends whichever previous choice it doesn't go below.
+- **只记一段、贪心挑能接上的较小值**。贪心会一直守着当前这段，不肯在较大的值后面断开、换成较小的值重新开始。`nums1 = [2, 1, 1, 1]`、`nums2 = [2, 2, 1, 1]` 时，贪心选成 `[2, 2, 1, 1]`，最长 2。正确选法是 `[2, 1, 1, 1]`，长度 3。实测暴力解和正确版本都给 3，贪心给 2。DP 同时保留两种结尾，才不会漏掉这种选法。
+- **只和同一个数组的上一位比**。写成 `nums1[i]` 只接 `nums1[i - 1]`、`nums2[i]` 只接 `nums2[i - 1]`，就漏了在两个数组之间来回换的选法。实测 `nums1 = [1, 3, 1]`、`nums2 = [3, 1, 4]`，正确答案是 3（选成 `[1, 3, 4]`），这个写法给 2。
+- **先改 `end_on_1`、再用它算 `end_on_2`**。分两行赋值时，算 `end_on_2` 拿到的是下标 `i` 的新 `end_on_1`，却拿它和 `nums1[i - 1]` 比。实测 `nums1 = nums2 = [1, 1]`，正确答案是 2，这个写法给 3，比数组还长。
更新题目 2771. Longest Non-decreasing Subarray From Two Arrays

body

meta
