问题描述 链接到标题

763.划分字母区间

解题思路 链接到标题

思路一 链接到标题

首先遍历一遍数组，记录每个字母在字符串中出现的最远位置。

声明一个变量right，用来记录已经遍历的字符中，最远的位置，当遍历到的位置与记录的最远位置重叠时，就说明可以划分数组了。

思路二 链接到标题

首先遍历一遍数组，记录每个字母出现的次数，并记录是否出现；

再遍历一次数组，当第一次碰到该字符时，该字符入栈，最后一次碰到该字符时，弹出栈顶的字符，栈空时，说明可以分割了。

代码 链接到标题

代码一 链接到标题 

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        for (int i = 0; i < S.size(); i++) {
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

代码二 链接到标题 

class Solution {
  public:
    vector<int> partitionLabels(string s) {
        vector<int> res;
        int arr[26] = {0};
        int arr_bool[26] = {0};
        int len = 0;
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            arr[s[i] - 'a']++;
            arr_bool[s[i] - 'a'] = 1;
        }
        for (int i = 0; i < s.size(); i++) {
            len++;
            arr[s[i] - 'a']--;
            if (arr_bool[s[i] - 'a'] != 0) {
                st.push(s[i]);
                arr_bool[s[i] - 'a'] = 0;
            }
            if (arr[s[i] - 'a'] == 0)
                st.pop();
            if (st.empty()) {
                res.push_back(len);
                len = 0;
            }
        }
        return res;
    }
};