洛谷P1106题【删除K个数字得到最小数】解题思路与C++代码详解

一、题目解读

洛谷P1106题要求给定一个数字串num和整数k，通过删除num中的k个数字，得到一个最小的可能结果。题目需注意处理前导零（如删除后全为0需返回"0"）及数字串本身的非负特性。核心在于如何在删除操作中保持数字顺序并最小化结果。

二、解题思路

采用单调栈优化策略：

1. 维护一个单调递增的栈，从num左到右遍历数字。

2. 若栈顶数字大于当前数字且k未用完，则弹出栈顶（删除较大数），直至栈顶小于等于当前数字或k耗尽。

3. 遍历结束后，若k仍有剩余，从栈末尾删除对应数字（末尾数字对结果影响最小）。

4. 去除栈中元素构成的新串的前导零，确保结果合法。

三、解题步骤

1. 初始化：创建栈存储数字，k记录剩余删除次数。

2. 遍历数字串：

○ 若栈不空且栈顶>当前数字且k>0，弹出栈顶并k减1。

○ 将当前数字入栈。

3. 处理剩余k：若k未耗尽，从栈末尾弹出对应元素。

4. 构建结果：去除前导零后拼接栈中元素，空串则返回"0"。

四、代码与注释

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 删除k个数字得到最小数
string removeKDigits(string num, int k) {
    vector<char> stack;  // 单调栈，存储递减序列
    
    for (char digit : num) {  // 遍历数字串
        while (!stack.empty() && k > 0 && stack.back() > digit) {  // 若栈顶大于当前数字且可删除
            stack.pop_back();  // 弹出栈顶（删除较大数）
            k--;
        }
        stack.push_back(digit);  // 当前数字入栈
    }
    
    while (k-- > 0) {  // 处理剩余k：末尾删除
        stack.pop_back();
    }
    
    string result;
    bool leadingZero = true;  // 标记前导零
    for (char digit : stack) {
        if (leadingZero && digit == '0') continue;  // 跳过前导0
        leadingZero = false;
        result += digit;
    }
    return result.empty()? "0" : result;  // 空串返回0
}

int main() {
    string num;
    int k;
    cin >> num >> k;
    cout << removeKDigits(num, k) << endl;
    return 0;
}

五、总结

本解法通过单调栈巧妙地将删除操作转化为栈维护问题，核心逻辑在于“优先删除较大的数字以保留较小数字的左侧位置”，时间复杂度O(n)，适用于需优化数字序列的算法场景。需特别注意前导零处理以避免结果错误。