2022-1-5队列/栈day5

单调栈运用在除重

题1:

316. 去除重复字母labuladong 题解思路

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

注意:该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

 

示例 1:

输入:s = "bcabc"
输出"abc"

示例 2:

输入:s = "cbacdcbc"
输出:"acdb"

 

提示:

  • 1 <= s.length <= 104
  • s 由小写英文字母组成
 1 class Solution {
 2     public String removeDuplicateLetters(String s) {
 3         int[] cnt=new int[26];
 4         for (char a:s.toCharArray()){
 5             cnt[a-'a']++;
 6         }
 7         Stack<Character> stack=new Stack<>();
 8         int[] flag=new int[26];
 9         for (char a:s.toCharArray()){
10             if (flag[a-'a']!=0) {
11                 cnt[a-'a']--;
12                 continue;
13             }
14             while (!stack.isEmpty()&&stack.peek()>a&&cnt[stack.peek()-'a']>=2) {
15                 char c=stack.pop();
16                 cnt[c-'a']--;
17                 flag[c-'a']--;
18             }
19             stack.push(a);
20             flag[a-'a']++;
21         }
22         StringBuilder sb=new StringBuilder();
23         while (!stack.isEmpty()){
24             sb.append(stack.pop());
25         }
26         return sb.reverse().toString();
27     }
28 }

思路:cnt数组记录字符串所有字母的数量,flag数组记录当前栈内字母的数量。遍历字符串时,当当前字母加入后字典序会变小且出栈的字母后续还有时(除了出栈的一个还有一个,即数量超过2),栈弹出栈顶元素,同时更新字母的数量。此外,如果当前栈内已经有相同的字母,需要跳过,注意要更新计数。不能出栈时,添加当前字母入栈,更新计数。

优化:可以直接用stringbuffer模拟栈,因为只需要操作头部。

上一篇:2022-1-18图day5


下一篇:第三周 Day5