单调栈运用在除重

题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模拟栈，因为只需要操作头部。