最大新整数

题解

题目难度：中等难度

知识点：单调栈

单调栈说明

定义：

单调栈就是栈内元素递增或者单调递减的栈，并且只能在栈顶操作。单调栈的维护是O(n)

的时间复杂度，所有元素只会进进栈一次

性质：

单调栈里面的元素具有单调性；

元素加入栈前会把栈顶破坏单调性的元素删除；

使用单调栈可以找到元素向左遍历的第一个比他小的元素（单增栈），也可以找到元素向左遍历第一个比他大的元素（单减栈）；

一般使用单调栈的题目具有以下的两点：

离自己最近（栈的后进先出的性质）
比自己大（小）、高(低)；

解题思路：

1.将字符串中所有元素从头开始，在压入栈前，判断栈顶元素与该元素大小：

如果栈顶元素大于该元素，直接压入栈中；

如果栈顶元素小于该元素，判断k是否大于0（是否还需要删除元素），若大于0,删除栈顶元素，继续与新栈顶元素进行判断。若小于0，直接压入栈中。使栈成为一个单增栈。

2.若k>0（表示没有删除足够的元素），栈顶元素最小，直接将末尾k 个元素弹出。

3.将栈中元素依次弹出，其反序为最终结果。

#include<iostream>
#include<stack>
using namespace std;
void cout1(stack<char> &s){
    if(s.empty()==1) return;
    char top=s.top();
    s.pop();
    cout1(s);
    cout<<top;
}
int main(){
    string str;
    int k;
    stack<char> s;
    cin>>str>>k;
    s.push(str[0]);
    for(int i=1;i<str.length();i++){
        while(s.empty()==0&&s.top()<str[i] && k>0){
            s.pop();
            k--;
        }
        s.push(str[i]);
    }
    while(k!=0){
        s.pop();
        k--;
    }
    cout1(s);
    return 0;
}