牛客13271 保留最大的数贪心策略应用如何删除数字保留最大值？

5个月前 (06-20)牛客题解196

1. 问题理解与算法选择

这道题属于典型的贪心算法应用场景。我们需要在每一步做出局部最优选择，以期达到全局最优解。具体来说，就是每次遇到一个数字时，决定是否保留它，使得最终结果尽可能大。

2. 核心算法思路

算法采用栈数据结构来实现贪心策略：

遍历数字字符串
当当前数字比栈顶数字大时，弹出栈顶数字（删除操作）
将当前数字压入栈中
最后处理可能剩余的删除操作

3. 关键点解析

贪心策略的正确性：为什么删除较小的数字能得到最大结果？因为数字的高位对数值大小影响更大
栈的使用：栈帮助我们方便地比较和操作最近处理的数字
边界条件处理：包括全零情况、删除所有数字的情况等

4.完整代码

#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;
}