洛谷P1106题解：贪心策略与单调栈实现删除k位最小数

7个月前 (08-15)洛谷题解352

字符串处理与贪心算法的结合常常考验我们对问题本质的理解。本文将以洛谷P1106题为例，详细介绍如何通过贪心算法删除k位数字使剩余数字最小，帮助新手掌握单调栈和贪心算法的应用技巧。

一、问题解析

题目要求给定一个字符串表示的数字和一个整数k，删除其中k位数字，使得剩余数字形成的数最小。核心挑战在于：

必须删除恰好k位数字
数字顺序不能改变
需要去除结果中的前导零
处理结果为空的情况

‌贪心策略核心思想‌：

‌局部最优导致全局最优‌：尽可能让高位的数字变小
‌单调栈处理‌：维护一个单调不降的序列
‌前导零处理‌：删除结果中开头的所有零

二、完整代码

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

// 删除k位数字的函数
string removeKDigits(string num, int k) {
    // 使用vector模拟栈结构
    vector<char> stack;
    
    // 遍历输入数字的每一位
    for (char digit : num) {
        // 贪心策略：当栈非空、还有删除次数且栈顶数字大于当前数字时
        while (!stack.empty() && k > 0 && stack.back() > digit) {
            stack.pop_back(); // 删除栈顶数字（删除高位较大的数字）
            k--; // 减少剩余删除次数
        }
        // 将当前数字加入栈中
        stack.push_back(digit);
    }
    
    // 如果还有k需要删除，从末尾删除（此时栈中已是单调不减序列）
    while (k-- > 0) {
        stack.pop_back(); // 删除末尾较大的数字
    }
    
    // 构建结果字符串并去除前导零
    string result; // 存储最终结果
    bool leadingZero = true; // 标记是否处于前导零状态
    
    // 遍历栈中每个数字
    for (char digit : stack) {
        // 跳过前导零
        if (leadingZero && digit == '0') continue;
        // 遇到非零数字或已有非零数字，结束前导零状态
        leadingZero = false; 
        result += digit; // 将数字添加到结果
    }
    
    // 处理结果为空的情况（如删除所有数字）
    return result.empty() ? "0" : result;
}

int main() {
    string num; // 存储输入的数字字符串
    int k;      // 要删除的数字位数
    cin >> num >> k; // 读取输入
    
    // 调用函数并输出结果
    cout << removeKDigits(num, k) << endl;
    return 0;
}