LeetCoden位数字，移除其中k位，使得结果最小-创新互联

原题链接

更新：基本一样的的题目1673. 找出最具竞争力的子序列

class Solution {public:
    vectormostCompetitive(vector& nums, int k) {int cnt = nums.size() - k;

        stackstk;
        for(int& x : nums) {while(stk.size() && cnt >0 && stk.top() >x) stk.pop(), cnt -- ;
            stk.push(x);
        }

        while(cnt --) stk.pop();
        vectorres;
        while(stk.size()) res.push_back(stk.top()), stk.pop();
        reverse(res.begin(), res.end());
        return res;
    }
};

• n位数字，移除其中k位，使得结果最小。
• • C++代码
  • 思路
  • 算法(单调栈)
  • 算法复杂度
  • C++代码

不难发现，对于相同前缀的两个数字 34 x 34x 34x和 34 y 34y 34y，如果 x < y x< y x

那我们就可以知道：要求最终的结果最小，那么前缀中的数字要尽可能的小。我们知道“小”是相对的，也就是我们需要来选择这个数中的哪些数字要被保留下来，成为”小“的数字。

我们来考虑这样一种情况，对于下标 i i i上的数字 d i g i t digit digit，如果他左边（下标 < i 算法(单调栈)

到这里我们就需要考虑每一个数字的前面哪些较大的数，并且能够将他们移除（移除的次数 k k k需要大于0），我们可以用一个栈来维护这个数字序列，枚举该序列，假设当前枚举的数字为 x x x，判断栈顶的数字是否大于 x x x，如果大于，则弹出该栈顶元素，继续执行该过程，直到①栈中不存在数字_或者_②栈顶的数字不大于 x x x_或者_③ k = = 0 k == 0 k==0 这些情况的出现，接着我们将当前元素添加到栈中。

到这里我们需要来解释一下为什么只有栈顶的数字大于 x x x才考虑移除栈中的元素。

• 首先我们考虑栈顶元素小于当前元素的情况，如果我们选择移除栈顶元素，那么数字序列的前缀将变大，不符合题目要求，所以我们不应该移除栈顶元素。

• 如果当前元素等于栈顶元素，我们考虑紧接着要枚举到的元素 y y y，如果 x < y x< y x y x >y x>y，那么我们执行上一段中：

  判断栈顶的数字是否大于 x x x，如果大于，则弹出该栈顶元素。

  即可。

class Solution {public:
    string removeKdigits(string num, int k) {stackstk;
        for(auto& c : num) {int x = c - '0';
            while(stk.size() && k >0 && stk.top() >x) {stk.pop();
                k -- ;
            }
            stk.push(x);
        }

        while(k --) stk.pop();
        string res;
        while(stk.size()) res += stk.top() + '0', stk.pop();
        while(res.size() >1 && res.back() == '0') res.pop_back();
        if(res.size() == 0) res = '0';
        reverse(res.begin(), res.end());
        return res;
    }
};