C 語言刪數問題：經典遞迴/疊代解法與常見陷阱

題目描述（根據常見 OJ 題目重構）

給定一個正整數 n，從其十進位表示中刪除 k 個數字，使剩下的數字組成的新數**最小**（或最大），輸出結果。不允許改變剩餘數字的相對順序。

核心演算法：單調棧

為得到**最小**結果，維護一個單調遞增棧：

1. 遍歷每個數字 digit。
2. 而棧非空、棧頂 > digit、尚可刪除 (k > 0)：彈出棧頂，k--。
3. 將 digit 壓入棧。

遍歷結束若 k > 0，從棧尾刪除 k 個。棧內剩餘即為答案（去除前導零）。

C 語言實作

#include <stdio.h>
#include <string.h>

void deleteDigits(char *num, int k, char *result) {
    int n = strlen(num);
    char *stack = (char*)malloc(n + 1);
    int top = -1;

    for (int i = 0; i < n; i++) {
        while (top >= 0 && k > 0 && stack[top] > num[i]) {
            top--;
            k--;
        }
        stack[++top] = num[i];
    }
    // 仍有刪除額度，從尾部刪
    top -= k;
    if (top < 0) top = -1;

    // 複製結果並去除前導零
    int idx = 0;
    while (idx <= top && stack[idx] == '0') idx++;
    if (idx > top) { result[0] = '0'; result[1] = '\0'; }
    else {
        for (int i = 0; idx <= top; i++, idx++) result[i] = stack[idx];
        result[top - idx + 2] = '\0';
    }
    free(stack);
}

int main() {
    char num[100], res[100];
    int k;
    scanf("%s %d", num, &k);
    deleteDigits(num, k, res);
    printf("%s\n", res);
    return 0;
}

測試範例

輸入：1432219 3
過程：棧變化 1 → 1,4 → 1,3 → 1,2 → 1,2,2 → 1,2,1 → 1,2,1,9
刪除 3 位後棧頂：1219
輸出：1219

常見陷阱

• 前導零處理：結果全為零時輸出單一 0。
• k ≥ 長度：直接輸出 0。
• 輸入極長：使用動態配置或固定大緩衝區（如 100000+5）。
• 求最大值：改為單調遞減棧（棧頂 < digit 時彈出）。

遞迴解法（教學用，效率較低）

// 從 num[pos:] 選擇 n-k 位組成最小數
void dfs(char *num, int pos, int remain, char *path, int pathLen, char *best) {
    if (remain == 0) {
        path[pathLen] = '\0';
        if (strcmp(path, best) < 0) strcpy(best, path);
        return;
    }
    if (pos >= strlen(num)) return;
    // 選擇當前位
    path[pathLen] = num[pos];
    dfs(num, pos + 1, remain - 1, path, pathLen + 1, best);
    // 不選擇
    dfs(num, pos + 1, remain, path, pathLen, best);
}

總結

刪數問題標準解為 **O(n) 單調棧**，C 語言用字元陣列模擬棧最簡潔高效。注意前導零、k 過大等邊界條件即可 AC。