[数据结构][Python][经典题目][贪心算法]删除K个数字获得删除后的最小值

r囧r小猫 2023-10-11 13:08 4阅读 0赞

## 题目： ##

给出一个整数，从该整数中去掉K个数字，要求剩下的数字形成的新整数尽可能小  
假设给出一个整数1593212，删除三个数字，新整数的最小情况是1212  
30200，删去一个数字，新整数的最小情况是200

## 解题思路： ##

这个题目要求我们删除K个数字，我们不妨把问题简化一下，如果只删除一个数字，如何让新整数的值变得最小？  
这时我们可能会想到优先删除这组数字中最大的数字，但是这是不对的，举例说明：3549中删除9后是354，删除5后是349，所以不能这样想。  
数字的大小固然重要，但是数字的位置更加重要，一个整数的最高位哪怕减小1，对整个数字影响都很大。  
所以我们把原来的数从左到右进行比较，如果发现某一个数字比他右边的数字大，那么删除该数字后，必然会使该数位的值减小，因为右边比他小的数顶替了他。  
我们利用栈的特性，但不是利用栈，让所有数字依次入栈，当某个数字需要删除时，让该数字出栈，最后输出剩下的字符型结果  
下面以整数541270936，k=3为例

1.当遍历到数字5，数字5入栈  
原整数

<table> 
 <thead> 
  <tr> 
   <th>原整数</th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7</td> 
   <td>0</td> 
   <td>9</td> 
   <td>3</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

2.当遍历到数字4时，发现4<5，所以数字5出栈，数字4入栈。

<table> 
 <thead> 
  <tr> 
   <th>原整数</th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7</td> 
   <td>0</td> 
   <td>9</td> 
   <td>3</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

3.当遍历到数字1的时候，4>1,所以4出栈，1入栈

<table> 
 <thead> 
  <tr> 
   <th>原整数</th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7</td> 
   <td>0</td> 
   <td>9</td> 
   <td>3</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

4.然后遍历2，7，依次入栈

<table> 
 <thead> 
  <tr> 
   <th>原整数</th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7</td> 
   <td>0</td> 
   <td>9</td> 
   <td>3</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>2</td> 
   <td>7</td> 
   <td>–</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

5，遍历到0时，7>0,则栈顶的7出栈，0进行入栈

<table> 
 <thead> 
  <tr> 
   <th>原整数</th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7</td> 
   <td>0</td> 
   <td>9</td> 
   <td>3</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>2</td> 
   <td>0</td> 
   <td>–</td> 
   <td>–</td> 
   <td>—</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

6.我们的删除次数已经用完，将剩下数字一起写入栈中

<table> 
 <thead> 
  <tr> 
   <th>原整数</th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>4</td> 
   <td>1</td> 
   <td>2</td> 
   <td>7</td> 
   <td>0</td> 
   <td>9</td> 
   <td>3</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>2</td> 
   <td>0</td> 
   <td>9</td> 
   <td>3</td> 
   <td>6</td> 
   <td>–</td> 
   <td>–</td> 
   <td>–</td> 
  </tr> 
 </tbody> 
</table>

## 代码展示: ##

def removeKDigits(num,k):
        n = len(num)
        if n < k: return None
        stack = []
        for i in num:
            if not stack:
                stack.append(i)
                continue
            if k>0:
                while k>0 and stack:
                    if stack[-1]>i:
                        stack.pop()
                        k-=1
                    else:
                        break
            stack.append(i)
        if k!=0:
            return ''.join(stack[:-k])
        return ''.join(stack)
    
    if __name__ == '__main__':
        minNum = removeKDigits('541270936',3)
        print(minNum)

![在这里插入图片描述][20190923233327431.png]

[20190923233327431.png]: https://img-blog.csdnimg.cn/20190923233327431.png