南阳网站设计,十堰网站建设制作公司,wordpress公众号推送,安徽建设工程信息网人员去除重复字母 题目描述单调栈代码演示进阶优化 上期经典 题目描述 难度 - 中等 leetcode316. 去除重复字母 给你一个字符串 s #xff0c;请你去除字符串中重复的字母#xff0c;使得每个字母只出现一次。需保证 返回结果的字典序最小#xff08;要求不能打乱其他字符的相对… 去除重复字母 题目描述单调栈代码演示进阶优化 上期经典 题目描述 难度 - 中等 leetcode316. 去除重复字母 给你一个字符串 s 请你去除字符串中重复的字母使得每个字母只出现一次。需保证 返回结果的字典序最小要求不能打乱其他字符的相对位置。 示例 1 输入s “bcabc” 输出“abc” 示例 2 输入s “cbacdcbc” 输出“acdb” 提示 1 s.length 1e4 s 由小写英文字母组成 单调栈 题目要求总共有三点 要求一、要去重。 要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。 要求三、在所有符合上一条要求的去重字符串中字典序最小的作为最终结果。 根据要求三我们就能想到这题可以用单调栈用单调栈来保证字典序排列。 要求一我们要去重因此要加上出栈的条件。 只有在栈顶元素字典序靠后且在之后还有出现次数才弹出栈.同时压栈时应该注意栈中没有出现过该元素才能压栈. 若输入为bcacc b 入栈c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈a 入栈,因为 a 的字典序列靠前且a没有出现过,此时要考虑弹出栈顶元素. 元素 c 因为在之后还有 至少一次 出现次数所以这里可以弹出. 元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.c 入栈时依然因为字典序靠后且栈中没出现过直接压栈c 入栈时栈中已经出现过c,跳过该元素 输出结果为 bac 代码演示 String removeDuplicateLetters(String s) {StackCharacter sta new Stack();//只有小写字母所以可以用26长度就可以了int[] count new int[26];//统计每个字出现的次数方便判断何时可以出栈for (char c : s.toCharArray()){count[c - a];}boolean[] inStack new boolean[26];for (char c : s.toCharArray()){//每遍历一个元素就把字符出现的次数减一count[c - a]--;if (inStack[c - a]){continue;}//出栈的三个条件//栈内元素不为null//当前元素字典序小于之前入栈的元素//并且保证后面还有要弹出的元素如果后面没有了就不能弹出while(!sta.isEmpty() sta.peek() c count[sta.peek() - a] 0){inStack[sta.pop() - a] false;}sta.push(c);inStack[c - a] true;}StringBuffer sb new StringBuffer();while (!sta.isEmpty()){sb.append(sta.pop());}//栈先进后出因此打印结果时要先逆序return sb.reverse().toString();}进阶优化 上面解法中我们用栈去保存元素然后最后再倒进stringBuilder里其实我们一开始就可以用StringBuilder,去存储元素最后保留的结果就是要的答案 代码演示 String removeDuplicateLetters(String s) {StackCharacter sta new Stack();StringBuffer sb new StringBuffer();char[] chars s.toCharArray();int[] count new int[256];for (int i 0; i chars.length;i){count[chars[i] - a];}boolean[] inStack new boolean[26];for (char c : chars){count[c - a]--;if (inStack[c - a]){continue;}while(sb.length() 0 sb.charAt(sb.length() - 1) c count[sb.charAt(sb.length() - 1) - a] 0){inStack[sb.charAt(sb.length() - 1) - a] false;sb.deleteCharAt(sb.length() - 1);}sb.append(c);inStack[c - a] true;}return sb.toString();}上期经典
leetcode410. 分割数组的最大值
