从两个数组中构造最长非递减子数组
Longest Non-decreasing Subarray From Two Arrays
题目详情
问题：从两个数组中构造最长非递减子数组
考察：数组、动态规划
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/longest-non-decreasing-subarray-from-two-arrays
英文原题
Problem: Longest Non-decreasing Subarray From Two Arrays
Patterns: Array, Dynamic Programming
Recency: 2yr
Link: https://leetcode.com/problems/longest-non-decreasing-subarray-from-two-arrays
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：对每个位置维护两个状态：以 nums1[i] 结尾和以 nums2[i] 结尾的最长非递减连续长度。分别比较前一位置选 nums1/nums2 是否能接到当前选择。
复杂度：时间 O(n)，空间 O(1)。
英文解析
Approach: Keep two rolling states at each index: the best non-decreasing contiguous length ending by choosing `nums1[i]`, and the same length ending by choosing `nums2[i]`. Each current choice can extend either previous choice if the selected value is at least the previous selected value.
Complexity: Time , space .