网站域名切换/软文营销网

最小字典序模版

最小字典序单调栈思路解析

1. 问题定义

给定一个字符串 num 和一个整数 k，要求移除 k 个字符后，使剩下的字符串是所有可能结果中字典序最小的。

2. 关键观察

• 字典序特性：高位字符对字典序的影响大于低位字符。

• 贪心选择：为了得到最小字典序，应尽可能让高位字符保持较小值。

3. 单调栈的作用

• 维护单调递增栈：栈中存储字符，保证栈顶到栈底字符单调递增。

• 移除策略：

  • 当当前字符 s 小于栈顶字符且还可以移除字符（k > 0）时，弹出栈顶字符（相当于移除一个字符）。

  • 这样可以确保高位字符尽可能小。

4. 特殊处理

• 前导零：如果栈为空且当前字符是 '0'，则不压入栈（避免前导零）。

• 剩余移除：如果遍历完字符串后仍有 k > 0，直接从栈末尾移除 k 个字符（因为此时栈是单调递增的，末尾字符较大）。

#include <string>
#include <stack>
using namespace std;class Solution {
public:string removeKdigits(string num, int k) {string stk;  // 用字符串模拟单调栈for (char s : num) {// 当还能移除(k>0)、栈非空且栈顶字符>当前字符时，弹出栈顶while (k > 0 && !stk.empty() && stk.back() > s) {stk.pop_back();k--;}// 避免前导零：栈为空时不压入'0'if (!(stk.empty() && s == '0')) {stk.push_back(s);}}// 处理剩余的k（移除末尾的k个字符）while (k-- > 0 && !stk.empty()) {stk.pop_back();}// 栈为空时返回"0"，否则返回栈内容return stk.empty() ? "0" : stk;}
};

经典例题907. 子数组的最小值之和 - 力扣（LeetCode）

本文参考了力扣的灵山爱抚茶的题单分享｜【算法题单】单调栈（矩形面积/贡献法/最小字典序）- 讨论 - 力扣（LeetCode）