题解 | 保留最大的数

保留最大的数

https://www.nowcoder.com/practice/7f26bfeccfa44a17b6b269621304dd4a

解题思路

这是一个贪心算法题目。为了使保留下来的数字最大，我们需要：

从左往右遍历数字，每次删除一个数字时：
- 找到第一个比后面数字小的位置
- 删除该位置的数字
- 这样可以保证剩余数字最大
重复上述过程 $cnt$ 次，直到删除够指定数量的数字

代码

c++
java
python

#include <iostream>
#include <string>
using namespace std;

int main() {
    string number;
    int cnt;
    cin >> number >> cnt;
    
    string result;
    int n = number.length();
    
    // 每次删除一个数字
    for(int i = 0; i < n; i++) {
        // 当前数字比栈顶小，且还可以删除数字时，删除栈顶
        while(!result.empty() && cnt > 0 && result.back() < number[i]) {
            result.pop_back();
            cnt--;
        }
        result.push_back(number[i]);
    }
    
    // 如果还需要删除数字，从末尾删除
    while(cnt > 0) {
        result.pop_back();
        cnt--;
    }
    
    cout << result << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String number = sc.next();
        int cnt = sc.nextInt();
        
        StringBuilder result = new StringBuilder();
        int n = number.length();
        
        // 每次删除一个数字
        for(int i = 0; i < n; i++) {
            char c = number.charAt(i);
            // 当前数字比栈顶小，且还可以删除数字时，删除栈顶
            while(result.length() > 0 && cnt > 0 && 
                  result.charAt(result.length()-1) < c) {
                result.setLength(result.length()-1);
                cnt--;
            }
            result.append(c);
        }
        
        // 如果还需要删除数字，从末尾删除
        while(cnt > 0) {
            result.setLength(result.length()-1);
            cnt--;
        }
        
        System.out.println(result.toString());
    }
}

def solve():
    number = input()
    cnt = int(input())
    
    result = []
    n = len(number)
    
    # 每次删除一个数字
    for i in range(n):
        # 当前数字比栈顶小，且还可以删除数字时，删除栈顶
        while result and cnt > 0 and result[-1] < number[i]:
            result.pop()
            cnt -= 1
        result.append(number[i])
    
    # 如果还需要删除数字，从末尾删除
    while cnt > 0:
        result.pop()
        cnt -= 1
    
    print(''.join(result))

if __name__ == "__main__":
    solve()