LeetCode 763. 划分字母区间

Categories:

题目描述
思路分析
1. 解法一：贪心 + 最后出现位置（推荐）
相似题目

题目描述

✅ 763. 划分字母区间

思路分析

解法一：贪心 + 最后出现位置（推荐）

核心思路：

要让每个字母只出现在一个片段中，每个片段的右边界必须覆盖该片段内所有字母最后一次出现的位置。

预处理：遍历字符串，记录每个字母最后出现的下标 last[c]。

贪心划分：维护当前段的起点 start 和右边界 end，遍历字符串时不断将 end 更新为 max(end, last[s[i]])。

当 i == end 时，说明当前段已包含所有出现在此段中的字母，记录片段长度 end - start + 1，并将 start 移到 end + 1 开启新段。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串的长度，需要两次遍历。

空间复杂度：O(1)，字母表大小固定为 26，last 数组空间为常数。

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 记录每个字母最后出现的下标
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }

        List<Integer> result = new ArrayList<>();
        // start 为当前段起点，end 为当前段右边界
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 动态更新当前段的右边界
            end = Math.max(end, last[s.charAt(i) - 'a']);
            // 到达当前段右边界，记录片段长度
            if (i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
}

func partitionLabels(s string) []int {
    // 记录每个字母最后出现的下标
    last := [26]int{}
    for i, c := range s {
        last[c-'a'] = i
    }

    var result []int
    // start 为当前段起点，end 为当前段右边界
    start, end := 0, 0
    for i, c := range s {
        // 动态更新当前段的右边界
        if last[c-'a'] > end {
            end = last[c-'a']
        }
        // 到达当前段右边界，记录片段长度
        if i == end {
            result = append(result, end-start+1)
            start = end + 1
        }
    }
    return result
}

相似题目

题目	难度	考察点
56. 合并区间	中等	贪心、区间合并
57. 插入区间	中等	贪心、区间操作
435. 无重叠区间	中等	贪心、区间调度
452. 用最少数量的箭引爆气球	中等	贪心、区间覆盖
621. 任务调度器	中等	贪心、哈希表
738. 单调递增的数字	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/36092809