สร้างตัวเลขสูงสุดใน C++ (Create Maximum Number)

ภาพรวมปัญหา

ให้อาเรย์ตัวเลข 2 อาเรย์ (ความยาว m, n) สร้างตัวเลขที่ใหญ่ที่สุดความยาว k (k ≤ m+n) โดยรักษาลำดับสัมพัทธ์ภายในแต่ละอาเรย์

ตัวอย่าง

nums1 = [3,4,7,5], nums2 = [9,1,3,5,8,4], k = 5 → Output: [9,8,7,5,4]

วิธีแก้ปัญหา: Greedy + Stack + Merge

1. modify(v, k): เลือก k ตัวจาก v ให้ได้ตัวเลขมากที่สุด (รักษาลำดับ) — ใช้ Stack pop ตัวเล็กออกถ้ายังเหลือพอเติม
2. greater(a,b,i,j): เปรียบเทียบ lexicographical จากตำแหน่ง i,j
3. mergeThem(a,b): รวม 2 อาเรย์ที่เรียงดีแล้ว ให้ได้ตัวเลขมากที่สุด (เลือกหัวที่ใหญ่กว่า)
4. ลองทุกการแบ่ง k = i + (k-i) โดย i = 0..k, เลือกค่าที่มากที่สุด

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> mergeThem(vector<int> nums1, vector<int> nums2) {
        vector<int> ret;
        int i = 0, j = 0, n = nums1.size(), m = nums2.size();
        while (i < n || j < m) {
            if (greater(nums1, nums2, i, j)) { ret.push_back(nums1[i]); i++; }
            else { ret.push_back(nums2[j]); j++; }
        }
        return ret;
    }

    vector<int> modify(vector<int>& v, int k) {
        stack<int> st;
        vector<int> ret;
        for (int i = 0; i < v.size(); i++) {
            int x = v[i];
            while (!st.empty() && st.top() < x && st.size() + v.size() - i - 1 >= k) st.pop();
            if (st.size() < k) st.push(x);
        }
        while (!st.empty()) { ret.push_back(st.top()); st.pop(); }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    bool greater(vector<int>& a, vector<int>& b, int i, int j) {
        while (i < a.size() && j < b.size() && a[i] == b[j]) { i++; j++; }
        return j == b.size() || (i < a.size() && a[i] > b[j]);
    }

    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ret;
        int n = nums1.size(), m = nums2.size();
        for (int i = 0; i <= k; i++) {
            if (i <= n && (k - i) <= m) {
                vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i));
                if (greater(candidate, ret, 0, 0)) ret = candidate;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,4,7,5}, v1 = {9,1,3,5,8,4};
    // print_vector(ob.maxNumber(v, v1, 5));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O((m+n)k) — modify O(m+n), merge O(k), ลอง k แบบ
• พื้นที่: O(m+n)