Monotonic Stack and Lexicographical Merging
Intuition\n Describe your first thoughts on how to solve this problem. \nTo form the largest possible number of length k from two arrays while maintaining their
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo form the largest possible number of length `k` from two arrays while maintaining their relative order, we need to explore all possible ways of picking elements from both arrays. This involves generating the largest subarrays of different lengths from both arrays and then merging these subarrays to form the largest number. The main challenge is efficiently selecting and merging these elements to achieve the optimal result.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Splitting the Selection**:\n   - Iterate over all possible ways to split the selection of `k` elements between the two input arrays `nums1` and `nums2`. Specifically, for each `i` from `max(0, k - n)` to `min(k, m)`, `i` represents the number of elements taken from `nums1`, and `k - i` represents the number of elements taken from `nums2`.\n\n2. **Construct Maximum Subarrays**:\n   - For each split, use the `getMaxSubarray` function to construct the maximum subarray of a given length from both `nums1` and `nums2`.\n\n   - **`getMaxSubarray(array, subarrayLength)`**:\n     - This function constructs the maximum subarray of length `subarrayLength` from the given array using a monotonic stack approach.\n     - Traverse the array and use a stack to keep track of the maximum elements, ensuring that the remaining elements can still form a subarray of the required length.\n\n3. **Merge Subarrays**:\n   - Merge the two maximum subarrays into a single array while maintaining their order using the `mergeSubarrays` function.\n   - **`mergeSubarrays(subarray1, subarray2)`**:\n     - This function merges two subarrays into one, ensuring the largest possible lexicographical order.\n     - Traverse both subarrays and compare elements to construct the merged result, handling cases where elements are equal by comparing the remaining sequences.\n\n4. **Compare and Update**:\n   - Compare each merged result with the current best result and update the best result if the new merged array is lexicographically larger.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity is $$O(k \\cdot (m + n))$$, where `m` and `n` are the lengths of `nums1` and `nums2`, respectively, and `k` is the number of elements to be selected. This accounts for iterating over all possible splits and constructing/merging the maximum subarrays.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is $$O(m + n + k)$$, which includes the space for the maximum subarrays and the result array.\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        int m = nums1.size();\n        int n = nums2.size();\n        vector<int> res;\n\n        auto getMaxSubarray = [](const vector<int>& array, int subarrayLength) -> vector<int> {\n            vector<int> stack;\n            int remaining = array.size() - subarrayLength;\n            for (int num : array) {\n                while (!stack.empty() && remaining > 0 && stack.back() < num) {\n                    stack.pop_back();\n                    remaining--;\n                }\n                stack.push_back(num);\n            }\n            stack.resize(subarrayLength);\n            return stack;\n        };\n\n        auto mergeSubarrays = [](const vector<int>& subarray1, const vector<int>& subarray2) -> vector<int> {\n            vector<int> result;\n            int i = 0, j = 0;\n            while (i < subarray1.size() || j < subarray2.size()) {\n                if (j == subarray2.size() || (i < subarray1.size() && subarray1[i] > subarray2[j])) {\n                    result.push_back(subarray1[i++]);\n                } else if (i == subarray1.size() || (j < subarray2.size() && subarray2[j] > subarray1[i])) {\n                    result.push_back(subarray2[j++]);\n                } else {\n                    if (lexicographical_compare(subarray1.begin() + i, subarray1.end(), subarray2.begin() + j, subarray2.end())) {\n                        result.push_back(subarray2[j++]);\n                    } else {\n                        result.push_back(subarray1[i++]);\n                    }\n                }\n            }\n            return result;\n        };\n\n        for (int i = max(0, k - n); i <= min(k, m); i++) {\n            vector<int> maxSubarray1 = getMaxSubarray(nums1, i);\n            vector<int> maxSubarray2 = getMaxSubarray(nums2, k - i);\n            vector<int> candidate = mergeSubarrays(maxSubarray1, maxSubarray2);\n            if (lexicographical_compare(res.begin(), res.end(), candidate.begin(), candidate.end())) {\n                res = candidate;\n            }\n        }\n\n        return res;\n    }\n};\n\n\n```
['C++']