给定一个以字符串表示的非负整数 num, 移除这个数中的 k 位数字, 使得剩下的数字最小.
注意:
num 的长度小于 10002 且 ≥ k.
num 不会包含任何前导零.
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219.
- class Solution {
- public:
- // 得利用栈来解决. 思路是贪心: 1 4 3 2 2 1 9 其实当 num[i] <num[i-1] 时, 删除 num[i-1]
- string removeKdigits(string num, int k) {
- stack<char> s;
- int i=0;
- while(k&&i<num.size()){
- if(s.size()==0||s.top()<=num[i]){
- s.push(num[i]);
- i++;
- continue;
- }
- if(s.size()>0&&s.top()>num[i]){
- k--;
- s.pop();
- }
- }
- while(i<num.size()){
- s.push(num[i]);
- i++;
- }
- while(k){
- if(s.size()>0){
- k--;
- s.pop();
- }else{
- break;
- }
- }
- string res;
- while(s.size()){
- res.push_back(s.top());
- s.pop();
- }
- reverse(res.begin(),res.end());
- while(res.size()>0&&res[0] == '0'){
- res.erase(res.begin());
- }
- if(res.size() == 0){
- return "0";
- }
- return res;
- }
- };
优化
- class Solution {
- public:
- // 优化, 直接 把 result 结果作为栈使用
- string removeKdigits(string num, int k) {
- string result;
- for(int i=0;i<num.size();i++){
- while(result.size()>0&&k>0&&num[i] <result.back()){
- result.pop_back();
- k--;
- }
- if(result.size()==0&&num[i]=='0')
- continue;
- result.push_back(num[i]);
- }
- while(k&&result.size()>0){
- k--;
- result.pop_back();
- }
- if(result == ""){
- return "0";
- }
- return result;
- }
- };
来源: http://www.bubuko.com/infodetail-3609499.html