LeetCode 763. 划分字母区间

题目链接

763. 划分字母区间

题目分析

这个题的话，第一眼看还没啥思路，忘了10+分钟才有点想法。。
题目总体的话就类似我们维护一个窗口，不断去拓展这个窗口的右边界，直到当前窗口内的所有字符最后一次出现的位置都在右边界内。
但是在维护的时候要注意下面几个点

• 如果第一次寻找右边界的时候，字符在串中只出现了一次，要单独进行处理
• 如果相同的字符是相邻出现的话，我们内部的while循环需要写成l <= r，因为我们的l = i + 1，如果不判断相等的情况下，会导致漏判

总体的想法就这样了，写出来的结果好像还行？

代码实现

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<>();
        int i = 0;
        while(i < S.length()){
            int r = S.indexOf(S.charAt(i), i + 1);
            if(r == -1){
                res.add(1);
                i++;
                continue;
            }
            int l = i + 1;
            while(l <= r){
                int temp = S.indexOf(S.charAt(l), l + 1);
                r = Math.max(temp, r);
                l++;
            }
            res.add(r - i + 1);
            i = r + 1;
        }
        return res;
    }
}

通过截图