最小字典序字符串

4.1 B 最小字典序字符串

题目概括一下是给一个串s, 提供两个空串t,u。通过一下两个操作：

• s的第一个字符移动到t末尾
• t的最后一个字符移动到u末尾 求出能得到的最小字典序。

贪心+栈的题目, 对于结果u串, 当前位置上的字符要么从s串中来, 要么从t串中来。 若u任意位置上的选择都是最小的, 那么总的字典序也是最小的 证明：

u1: ... ... ... a ... ... 
u2: ... ... ... b ... ...

若 a 的字典序小于 b 的字典序, 那么根据字典序的定义, u1的字典序就小于u2的字典序。u1才是正确结果。

当前位置可以从s串和t串中来：

• 若s串存在能选的最小元素小于t串末尾, 则将其以及之前的字符都加入到t串, 并把该元素从t串末尾移到u串末尾
• 若大于等于, 则把t串末尾放到u串末尾

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
char s[N], u[N], t[N];
int top_u = -1, topt = -1;
char min_c[N];
int n;
 
int main()
{
    cin >> s;
    n = strlen(s);
    min_c[n] = 'z';
    for (int i = n - 1; i >= 0; i--)
        min_c[i] = min(s[i], min_c[i + 1]);
 
    for (int i = 0, j = 0; i < n; i = j)
    {
        if (topt == -1 || t[topt] > min_c[i])
        {
            for (j; s[j] != min_c[i] && j < n; j++)
                t[++topt] = s[j];
            u[++top_u] = min_c[i];
            j++;
        }
        else
            u[++top_u] = t[topt--];
    }
    while (topt != -1)
        u[++top_u] = t[topt--];
    cout << u << endl;
 
    return 0;
}