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

时间：2022-11-14 15:21:00

题意

题目如题，输入序列只包含小写字母，数据范围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)的方法考虑一波单调栈的意识。

相关知识

单调栈

  • 定义：栈中的元素是按照某种方式排列，但是必须是单调的。如果某元素破坏了栈的单调性，就弹出栈的元素，直到该元素满足栈的单调性为止。
  • 用途：使用单调栈可以找到元素向左遍历第一个比他小/大的元素，也可以找到元素向左遍历第一个比他大/小的元素，且时间复杂度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

相关文章