数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 中移除 K 个数字
假设我们有一个用字符串表示的非负整数 num，我们需要从中移除 k 个数字，使得新的数字尽可能小。例如，如果输入是“1432219”且 k = 3，则结果将是“1219”。
为了解决这个问题，我们将遵循以下步骤：
定义一个栈 st，创建一个空字符串 ret
n := num 的长度
对于 i 从 0 到 n – 1
当 k 不为零且栈不为空且栈顶 > num[i]
从栈中删除元素并将 k 减 1
将 num[i] 插入到 st 中
当 k 不为 0 时，从栈中删除元素
当栈不为空时
ret := ret + 栈顶元素，从栈中删除元素
现在反转 ret 字符串
ans := 一个空字符串，i := 0
当 i < ret 的长度且 ret[i] 不为 ‘0’
将 i 加 1
对于 i < ret 的长度
ans := ans + ret[i]
ret := ans
如果 ret 的长度为 0，则返回“0”，否则返回 ret
示例 (C++)
让我们来看下面的实现，以便更好地理解：
class Solution {
public:
string removeKdigits(string num, int k) {
stack st;
string ret = "";
int n = num.size();
for(int i = 0; i < n; i++){
while(k && !st.empty() && st.top() > num[i]){
st.pop();
k--;
}
st.push(num[i]);
}
while(k--)st.pop();
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
string ans = "";
int i = 0;
while(i <ret.size() && ret[i] == '0')i++;
for(; i < ret.size(); i++)ans += ret[i];
ret = ans;
return ret.size() == 0? "0" : ret;
}
};输入
"1432219" 3
输出
"1219"
更新于：2020年3月31日
627 次浏览
广告