二者其实十分相似。最近两周做了两道题都是单调栈和单调队列的典型应用，拿出来复习复习。

402. Remove K Digits

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

解答

表面上要求是移除k个数字，实则挑剩下num.size() - k位数字保持原序使其最小。

对于一个十进制数字（假设8位）$num = (x_7x_6x_5x_4x_3x_2x_1x_0)_{10}$。贪心具体证明略过，我们要使得小的数字尽可能在前面，这样就可以使最终得到的数字最小。

所以我们从左往右扫描，维护一个单调栈stack。这样我们可以获得$num$位数排列成的稳定的单调递增序列。我们在将第k位后面的数字pop()，就得到最终结果了。

class Solution {
public:
    string removeKdigits(string num, int k) {
        std::stack<int> s;
        for (char &ch : num) {
            int nch = ch - '0';
            while (!s.empty() && s.top() > nch && k) {
                k--;
                s.pop();
            }
            s.push(nch);
        }
        while (k > 0 && !s.empty()) {
            s.pop();
            k--;
        }
        string ans;
        while (!s.empty()) {
            ans += (char)(s.top() + '0');
            s.pop();
        }
        reverse(ans.begin(), ans.end());
        int index = 0;
        while (ans[index] == '0') {
            index++;
        }
        ans = ans.substr(index);
        return (ans == "" ? "0" : ans);
    }
};

谁是最佳选手

这题找不到出处。题干如下：

某视频网站举办了一个综艺节目，每周会有一名新选手加入节目，并根据才艺表现获得分数。

从第k+1周开始，最早加入节目的选手离开。

从第k周开始，得分最高的选手会获得“最佳选手”称号，请从第k周开始，找出每周“最佳选手”的分数。

输入：第一行包含两个整数n和k(2 <= k < n <= 30000)，n表示选手总人数，k表示从第k周开始评选“最佳选手"；第二行包括n个整数，表示每位选手初登节目时获得的分数。

输出：包括n-k+1行数据，分别是从第k周开始，到第n周结束，每周“最佳选手”的分数。

解答

又要最大值，又要保证顺序，暴力解答那是肯定超时的。我们需要使用单调队列来贪心。假设目前队列 $q = [1,2,4,3]$，我们可以发现1和2永远不可能获得称号，因为在他们被淘汰前他们怎么也不可能压过4。所我们可以通过维护单调队列来保证最佳选手次序。但是问题来了，第k周开始每周都要淘汰一个选手，我们的单调队列如果存放的是选手分数那我们很难维护队列的dequeue。所以，我们的队列存放选手的编号，额外建立一个std::vector<int> scores来存放选手分数，只要队首元素a满足

$$a + k \leq 2$$

说明他到了淘汰的时候了，这时候我们进行dequeue操作。

答案如下：

#include <iostream>
#include <queue>
#include <vector>

int main() {
    int k, n;
    std::cin >> n >> k;
    std::deque<long> man;
    std::vector<int> scores;
    for (long i = 0; i < n; i++) {
        long a;std::cin>>a;
        scores.push_back(a);
        while (!man.empty() && scores[man.back()] < a) {
            man.pop_back();
        }
        if (!man.empty() && man.front() <= i - k) {
            man.pop_front();
        }
        man.push_back(i);
        if (i >= k - 1) std::cout << scores[man.front()] << std::endl;
    }
}

这道题与第四周做的Daily Temperatures 有异曲同工之妙，都是用单调栈或单调队列存下标，可以对比学习。