给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 示例 1 :
输入: num = "1432219", k = 3 输出: "1219" 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。 示例 2 :
输入: num = "10200", k = 1 输出: "200" 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 :
输入: num = "10", k = 2 输出: "0" 解释: 从原数字移除所有的数字,剩余为空就是0。 通过次数39,267提交次数124,604
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-k-digits 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
因为 数子的 排列顺序 是不变的 只能删除 中间的 部分值
如果 后面的数比前面的 小,那么就可以删掉,这样剩下的部分数是小的,是单调递增的
如果删除的数量达到了,就可以返回
如果删除的数量没有达到,就删掉后面的 数 因为是单调递增 后面的数 是最大的
从 数学角度上看 就是前面小 ,权值大,肯定数最小
class Solution {
public:
string removeKdigits(string num, int k) {
vector<char> stk;
for (auto& digit: num) {
while (stk.size() > 0 && stk.back() > digit && k) {
stk.pop_back();
k -= 1;
}stk.push_back(digit);
}
for (; k > 0; --k) stk.pop_back();
string ans = "";
bool isLeadingZero = true;
for (auto& digit: stk) {
if (isLeadingZero && digit == '0') continue;
isLeadingZero = false;
ans += digit;
}
return ans == "" ? "0" : ans;
}
};