從大數中刪除 m 位得到最大值：貪心單調棧 / 區間最大值法完整解析

問題描述

給定一個最多 100 位的大整數 n (首位非 0) 和整數 m (m < 位數)，刪除 m 個數字，剩餘數字保持原順序組成新數，使新數最大。多組測試數據。

核心貪心策略：逐位選最大

結果長度 k = len - m。從左到右決定每一位：
第 1 位從原數前 len - k + 1 位中選最大 (且取最左的最大值)；
第 2 位從上一選位之後、前 剩餘長度 - 剩餘需選位數 + 1 範圍選最大；
以此類推。這保證高位盡可能大，且留足空間給後續位。

算法流程

1. 讀入字符串 s，長度 len，需保留 k = len - m 位。
2. start = 0，end = len - k (第一輪搜索右邊界)。
3. 循環 k 次：
   • 在 s[start..end] 中找最大字符 maxChar 及其最左位置 pos。
   • 輸出 maxChar。
   • start = pos + 1，end++ (下一輪右邊界右移一位)。

正確性直觀證明

若某位選擇非區間最大值，則存在更大數字在該區間內，將其換上必得到更大結果 (高位優先)。取最左最大值保證留給後續位最多選擇空間。

代碼實現 (C++)

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        string s; int m; cin >> s >> m;
        int len = s.length(), k = len - m;
        int start = 0, end = len - k; // 第一輪右邊界
        string ans;
        for (int i = 0; i < k; ++i) {
            char mx = '0'; int pos = start;
            for (int j = start; j <= end; ++j)
                if (s[j] > mx) { mx = s[j]; pos = j; }
            ans += mx;
            start = pos + 1;
            ++end; // 下一輪多一個候選位置
        }
        cout << ans << '\n';
    }
    return 0;
}

錯誤案例分析

原始嘗試：統計各數字出現次數，從 9 到 0 刪除。反例 14593, m=3：該法輸出 59，實際最優 93。原因：只保證「保留的數字集合最大」，忽略了順序約束導致的「數值最大」。

複雜度

時間 O(len × k) ≤ O(100²)，空間 O(1)，極易通過。