链接：https://ac.nowcoder.com/acm/contest/20960/1036
来源：牛客网

题目描述

给定字符串s，s只包含小写字母，请求出字典序最大的子序列。
子序列：https://en.wikipedia.org/wiki/Subsequence
字典序：https://en.wikipedia.org/wiki/Lexicographical_order

输入描述: 

一行一个字符串s (1 <= |s| <= 100,000)。

输出描述: 

字典序最大的子序列。
示例1

输入 

ababba

输出 

bbba
示例2

输入 

abbcbccacbbcbaaba

输出 

cccccbba
本题要求字典序最大的子序列，要求字典序最大自然每次都要取序列里面最大的那一个字母。为了快速找到最大的那个字母，采用指针优化的方式先从后向前遍历将某个下标后面最大的字母和下标记录下来，这样遍历的时候可以快速跳跃。
AC代码： 
#include <bits/stdc++.h>


using namespace std;

struct Node{
    char maxc;
    int maxpos;
};

Node a[100001];

int main() {
    string s;
    cin>>s;
    char maxc = 'a'-1;
    int maxpos = -1;
    for (int i=s.size()-1;i>=0;i--) {
        a[i].maxc = maxc;
        a[i].maxpos = maxpos;
        if (s[i]>=maxc) {
            maxc = s[i];
            maxpos = i;
        }
    }
    for (int i=0;i<s.size()&&i!=-1;) {
        if (i==0&&s[i] == maxc) cout<<s[i];
        else if (i!=0) cout<<s[i];
        i = a[i].maxpos;
    }
    return 0;
}