Maximize the Remaining String（单调栈）

传送门

题意：字符串去重，使得字符串字典序最大

---

思路:单调栈，预处理找到字符串中字符最后出现的位置。从左到右扫描当前字符串，若栈顶元素<当前元素，并且后续出现过，则出栈。

package csp;

import java.io.*;
import java.util.*;

public class MaximizeTheRemainingString {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner(new BufferedInputStream(System.in));
		int n=cin.nextInt();
		while(n--!=0)
		{
			int t[]=new int [150];
			boolean f[]=new boolean [150];
			String string=new String();
			string=cin.next();
			for(int i=0;i<string.length();i++) t[string.charAt(i)]=i;
			Stack<Character>stack=new Stack<>();
			stack.push(string.charAt(0));
			f[string.charAt(0)]=true;
			int i=1,len=string.length();
			while(!stack.empty() &&i<len)
			{
				Character top=stack.peek();
				Character current=string.charAt(i);
				if(f[current]) {
					i++;continue;
				}
				while(top<current && i<t[top] && !stack.empty())
				{
					stack.pop();
					f[top]=false;
					if (stack.size()!=0) {
						top=stack.peek();
					}
				}
				if(!f[current]) {
					f[current]=true;
					stack.push(current);
				}
				i++;
			}
			for(Character c:stack)
			{
				System.out.print(c);
			}
			System.out.println();
		}
	}
}