当前位置：首页 > 牛客 > 牛客13271题「删除K个数字的最小数」解题报告：贪心算法与栈的应用（附代码注释）

牛客13271题「删除K个数字的最小数」解题报告：贪心算法与栈的应用（附代码注释）

1个月前 (06-11)

一、题目解读

牛客13271题要求从给定的数字字符串中删除K个数字，使得剩余数字按原顺序排列后得到的最小数。题目核心在于如何在保持数字相对顺序的前提下，通过删除操作得到最优解。需注意结果字符串可能包含前导零，需根据规则处理。

二、解题思路

采用贪心算法与栈的数据结构。核心思想是维护一个单调递增的栈：

1. 遍历数字串，若当前数字比栈顶数字大且剩余可删除次数（K）足够，则弹出栈顶数字，减少K；

2. 若数字递增（如"1234"需删2个），需额外处理末尾数字；

3. 最终栈中剩余数字逆序拼接为结果，并处理前导零。

三、解题步骤

1. 初始化栈：创建栈存储数字字符，初始化K为删除次数。

2. 贪心处理：遍历每个字符，若栈不空且当前字符>栈顶且K>0，则弹出栈顶并减K，直至不满足条件。

3. 删除剩余K次：若K仍有剩余且栈不空，直接弹出栈顶（处理递增序列）。

4. 构建结果：逆序拼接栈中字符为结果串。

5. 处理前导零：若结果全为0，返回"0"；否则截取首个非零字符后的子串。

四、代码与注释

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

string removeKDigits(string num, int k) {
    stack<char> stk; // 维护单调递增栈
    
    for (char digit : num) { // 遍历数字串
        // 贪心策略：当前数字比栈顶大时弹出栈顶
        while (!stk.empty() && k > 0 && digit > stk.top()) {
            stk.pop(); // 弹出栈顶
            k--; // 减少删除次数
        }
        stk.push(digit); // 入栈当前数字
    }
    
    // 处理递增序列末尾需额外删除的情况
    while (k-- > 0 &&!stk.empty()) {
        stk.pop();
    }
    
    // 构建结果字符串
    string result;
    while (!stk.empty()) {
        result = stk.top() + result; // 逆序拼接
        stk.pop();
    }
    
    // 处理前导零（根据题目要求可能需要保留）
    size_t nonZero = result.find_first_not_of('0');
    if (nonZero!= string::npos) {
        result = result.substr(nonZero);
    } else {
        result = "0";
    }
    
    return result.empty()? "0" : result;
}

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