网络异常，图片无法展示
|
「这是我参与2022首次更文挑战的第15天，活动详情查看：2022首次更文挑战」
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入： S = "ababcbacadefegdehijhklij" 输出： [9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。 复制代码
提示：
S的长度在[1, 500]之间。S只包含小写字母'a'到'z'。
解题思路
本题要求划分片段的时候同一个字母，只能出现在一个片段中，所以针对单个字母，我们可以找到它第一次出现的位置，和最后一次出现的位置，这样的一个区间划分为一个片段，就保证了它只出现在一个片段中。
但是因为这样的区间中可能会有其他的字母，所以我们也要保证其他的字母只出现在一个片段中，那这个问题怎么解决呢？
这里我们可以遍历输入字符串，记录每一个字母第一次出现的下标和最后一次出现的下标，这样数组遍历完成，就得到了每个字母出现的开始位置和结束位置。
因为我们是从前向后遍历数组的，所以每个区间的开始位置是单调递增的。而这个时候，我们记录前面字母区间结束位置的最大值，当后续的区间的开始值大于前面区间结束值的最大值，就说明前面区间中的字母，在后续的区间中都不会再出现，这个时候，前面的区间就可以划分为一个单独的片段了。而这样一个片段的长度就是所有区间结束值的最大值减去开始值的最小值+1。每次找到一个片段后计算片段长度插入结果数组，当我们遍历完所有的字母区间，就得到了本题的结果。
代码实现
var partitionLabels = function (s) { // 创建map记录每个字母出现的开始结束下标 let map = new Map() // 遍历输入字符串，获取每个字母出现的开始结束下标 for (let i = 0; i < s.length; i++) { if (map.has(s[i])) map.get(s[i])[1] = i else map.set(s[i], [i, i]) } // 初始化结果数组 const res = [] // 记录可合并区间的开始下标和结束下标 let pre = 0, end = 0 // 遍历 map 拆分区间 map.forEach((item) => { // 获取当前字母出现的开始结束下标 const [a, b] = item // 如果当前字母的开始下标在待合并区间范围内，则当前字母要被合并到区间中 if (a <= end) end = Math.max(end, b) // 否则待合并区间可以合并为一个区间 else { res.push(end - pre + 1) // 初始化接下来的待合并区间的开始结束下标 pre = a end = b } }) // 将最后的待合并区间插入结果数组 res.push(end - pre + 1) // 返回结果数组 return res } 复制代码
至此我们就完成了 leetcode-763-划分字母区间
如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻
