【贪心】 LeetCode422. 移掉K位数字

﹏ヽ暗。殇╰゛Y 2022-12-03 13:21 105阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]

### 解答 ###

#include <iostream>
    #include <string>
    #include <list>
    #include <cassert>
    
    // 402. Remove K Digits
    
    // 贪心思想。从最高位开始，一个数一个数的压栈。只要高位的数比次高位的数小，
    // 那么就说明当前数更加小。如果高位的数比次高位的大，那么将高位的大的数移除掉，
    // 才能使数更小。
    std::string removeKdigits(const std::string& num, int k) { 
      std::list<char> min_number;
    
      if (num.empty()) { 
        return "0";
      }
    
      for (char digit : num) { 
        // 不断用栈顶的元素(也就是当前高位的数)和将要压栈的数进行比较。
        // 从第一位就开始这样比较，所以最终的每一位的结果都是符合条件的。
        while (!min_number.empty() && k > 0) { 
          // 如果栈中的数（高位的数）大于将要入栈的数，那么高位的数出栈。
          // 始终保持高位的数使最小的就可以了。
          if (min_number.back() > digit) { 
            min_number.pop_back();
            --k;
          } else { 
            break;
          }
        }
    
        if (min_number.empty() && digit == '0') { 
          continue;
        }
    
        min_number.push_back(digit);
      }
    
      while (k > 0 && !min_number.empty()) { 
        min_number.pop_back();
        --k;
      }
    
      std::string min_number_str;
      for (char min_digit : min_number) { 
        min_number_str.push_back(min_digit);
      }
    
      if (min_number.empty()) { 
        return "0";
      }
    
      return min_number_str;
    }
    
    int main() { 
      std::cout << removeKdigits("54321", 1) << std::endl;
      std::cout << removeKdigits("12345", 1) << std::endl;
      std::cout << removeKdigits("16543", 1) << std::endl;
      std::cout << removeKdigits("1", 1) << std::endl;
    
      std::cout << removeKdigits("54321", 2) << std::endl;
      std::cout << removeKdigits("12345", 2) << std::endl;
      std::cout << removeKdigits("16543", 2) << std::endl;
    
      std::cout << removeKdigits("165436", 3) << std::endl;
    
      std::cout << removeKdigits("10001", 1) << std::endl;
      std::cout << removeKdigits("10001", 3) << std::endl;
      std::cout << removeKdigits("10000", 3) << std::endl;
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/253588505cde4c5fa91bf0f97db4e2f1.png