[补题]找到原序列长度k的子序列中字典序最小的那个(单调栈)

题意

题目如题，输入序列只包含小写字母，数据范围0<k<=len<=500000。

例：

输入：helloworld

输出：ellld

题解

使用单调栈。当已删掉n-k个字符，输出栈中元素和剩余序列。否则当完成遍历一遍序列，输出栈底k个元素。时间复杂度O(n)。
我的思考
- 之前的思路是按序遍历26个字母，并遍历原序列的子区间(beg,end)其中beg是上一次找到的字符的下一个，end是不至于凑不够k的结尾处。写好并超时了。时间复杂度大概是O(k ·logn ·26)。
- 大概想的优化是排序/滑动窗口一样的东西搞成O(n),原因是单调栈并不知道什么时候用用的太少。
- 不知道怎么处理的点是找更新区间的最小字典序字符，以及字典序小但出现在结尾处的字符怎么处理(类似例子中的d)。单调栈+删掉n-k提前截止很好的处理了我两个不会处理的点。仔细体会吧。
- 起码下次要有优化到O(n)的方法考虑一波单调栈的意识。

代码

import java.util.Collections;

import java.util.LinkedList;

import java.util.Scanner;

import java.util.Stack;

public class subStr {

	public static void main(String args[]) {

		Scanner in=new Scanner(System.in);

		String str=in.next();

		int k=in.nextInt();		

		Stack<Character> stack=new Stack<>();

		int cntToDel=str.length()-k;

		for(int i=0;i<str.length();++i) {

			while(!stack.isEmpty()&&cntToDel!=0&&stack.peek()>str.charAt(i)) {

					stack.pop();

					--cntToDel;

			}

			//如果已经删了n-k个元素

			if(cntToDel==0) {

				LinkedList<Character> list=new LinkedList<>();

				while(!stack.isEmpty()) {

					list.add(stack.pop());

				}

				Collections.reverse(list);

				for(Character c:list) {

					System.out.print(c);

				}

				String tailStr=str.substring(i,str.length());

				System.out.print(tailStr);

				return;

			}

			stack.add(str.charAt(i));

		}

		//字符串完成了一遍遍历，输出单调栈底下的k个。

		LinkedList<Character> list=new LinkedList<>();

		while(!stack.isEmpty()) {

			list.add(stack.pop());

		}

		Collections.reverse(list);

		String subStr=str.substring(0,k);

		System.out.print(subStr);

	}

}

参考链接

https://blog.csdn.net/ljd201724114126/article/details/80663855

巴特西

[补题]找到原序列长度k的子序列中字典序最小的那个(单调栈)

题意

题解

相关知识

单调栈

单调队列

代码

参考链接

最新文章

热门文章