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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告