题解 | #分品种#

知识点

贪心

思路

首先逆序遍历预处理一遍数组，用end[26]数组维护每个字母最后出现的位置。 然后再遍历一次数组，假设每次放进去的片段左端点为l,右端点为r。

由题意可知，对于s[l~~r]片段内出现的字母，以后都不会再出现。

所以我们先考虑s[l]位置出现的最后位置r=end[s[l]-'a']。

然后，r是可以向右延伸的，取决于l~r之间的字母的新的出现的靠右的位置

（即更新r=max(r,end[s[i]-a])，其中l<=i<=r） 当更新到上界r仍不能再更新时，说明此时的片段内出现的字母以后不会再出现了，可以更新答案了。ans.push_back(r-l+1)即为长度。 然后l=r,开始对下一个区间片段的求r。

代码c++

#include <cstring>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型vector
     */
    vector<int> partitionLabels(string s) {
        // write code here
        int end[26 + 6];
        int n=s.size();
        for (int l = 0; l < 26; l++) {
            end[l] = -1;
        }

        for (int i = s.size() - 1; i >= 0; i--) {
            if (end[s[i] - 'a'] == -1)end[s[i] - 'a'] = i;
        }

        vector<int>ans;
        for (int l = 0; l <n; l++) {
        
           int r=end[s[l] - 'a'];
         //  cout<<i<<"  "<<r<<endl;
           int i=l;
           while(i<=r-1&&i<n-1)
           {
             i++;
             r=max(r,end[s[i]-'a']);
           }
           ans.push_back(r-l+1);
           l=r;
          

        }
        return ans;


    }
};