leetcode316. 去除重复字母(单调栈 - java)

这篇具有很好参考价值的文章主要介绍了leetcode316. 去除重复字母(单调栈 - java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

难度 - 中等
leetcode316. 去除重复字母

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

示例 1:
输入:s = “bcabc”
输出:“abc”

示例 2:
输入:s = “cbacdcbc”
输出:“acdb”

提示:
1 <= s.length <= 1e4
s 由小写英文字母组成

leetcode316. 去除重复字母(单调栈 - java),算法,java,数据结构,java,算法,数据结构,贪心算法,动态规划,决策树,leetcode

单调栈

题目要求总共有三点:
要求一、要去重。
要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。
要求三、在所有符合上一条要求的去重字符串中,字典序最小的作为最终结果。

根据要求三,我们就能想到这题可以用单调栈,用单调栈来保证字典序排列。
要求一,我们要去重,因此要加上出栈的条件。
只有在栈顶元素字典序靠后,且在之后还有出现次数才弹出栈.同时压栈时应该注意栈中没有出现过该元素才能压栈.

若输入为bcacc

  1. b 入栈
  2. c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈
  3. a 入栈,因为 a 的字典序列靠前且a没有出现过,此时要考虑弹出栈顶元素.
    元素 c 因为在之后还有 至少一次 出现次数,所以这里可以弹出.
    元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.
  4. c 入栈时依然因为字典序靠后且栈中没出现过直接压栈
  5. c 入栈时栈中已经出现过c,跳过该元素
    输出结果为 bac

代码演示

  String removeDuplicateLetters(String s) {

        Stack<Character> 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) {

        Stack<Character> 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. 分割数组的最大值文章来源地址https://www.toymoban.com/news/detail-685992.html

到了这里,关于leetcode316. 去除重复字母(单调栈 - java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法训练day37|贪心算法 part06(LeetCode738.单调递增的数字)

    题目链接🔥🔥 给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。 (当且仅当每个相邻位数上的数字 x 和 y 满足 x = y 时,我们称这个整数是单调递增的。) 示例 1: 输入: N = 10 输出: 9 示例 2: 输入: N = 1234 输出:

    2024年02月09日
    浏览(35)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(46)
  • 【leetcode:1944. 队列中可以看到的人数】单调栈算法及其相关问题

    1944. 队列中可以看到的人数 有  n  个人排成一个队列, 从左到右  编号为  0  到  n - 1  。给你以一个整数数组  heights  ,每个整数  互不相同 , heights[i]  表示第  i  个人的高度。 一个人能  看到  他右边另一个人的条件是这两人之间的所有人都比他们两人  矮  。更

    2024年01月25日
    浏览(36)
  • Java通过Lambda表达式根据指定字段去除重复数据(集合去重)

    这里博主给大家封装好了一个工具类,里面有两个方法。 方法一:可以根据指定字段去除重复数据。 方法二:可以获取到重复的数据。 大家在使用过程中直接拷贝下方代码在要去重的类中调用即可。 导入这个工具类后怎么使用呢?我们接着往下看。 List rstList = list.stream()

    2024年02月16日
    浏览(55)
  • 快速去重:使用Java根据对象某一属性去除重复对象的实现指南

    🧐📚 Java中的对象去重操作?跟着小编一起学习吧!👇 在处理对象集合时,有时候我们需要根据对象的某个属性进行去重操作。Java给我们提供了多种方法来实现这个功能。今天,小编就来给大家介绍一下如何使用Java根据对象的某个属性进行去重操作。💫 提供一个自定义的

    2024年02月04日
    浏览(65)
  • 算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树

    Leetcode 738.单调递增的数字 题目链接:738.单调递增的数字  大佬视频讲解:单调递增的数字视频讲解  个人思路 这个题目就是从例子中找规律,例如 332,从后往前遍历,32不是单调递增将2变为9,3减1,变成了329,遍历到2,32不是递增,将2变为9,3减1,变成299,符合题目条件,打印

    2024年04月16日
    浏览(46)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode667. 优美的排列 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必

    2024年01月25日
    浏览(52)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包