一道数组去重的算法题把我整不会了 :: labuladong的算法小抄

[labuladong]

文章链接点这里：一道数组去重的算法题把我整不会了

评论礼仪 见这里，违者直接拉黑。

[TinyOrange98]

数组去重的那道题目（leetcode316）可以仅从贪心的角度解决，无需借助单调栈：
1、首先遍历字符串建立一个从字符到下标映射的哈希表（代码中直接用数组+deque实现），对于字符x，其下标按照字符在字符串中出现的顺序存储在deque中。
2、然后统计字符串中去重后的字符个数。
3、字符串去重后的字符个数决定了最外层循环的执行次数，每枚举成功一次，cnt就减一。
4、内层循环中，首先尝试从字符 ’a‘ 开始寻找（待去重字符串，也就是区间[left_bound,n-1]对应的字符串，n是字符串长度）字典序最小的字符，然后判定该字符对应的最小下标y是否可满足（无需判断之后的下标，因为如果在区间[left_bound,y)中有不满足条件的字符，显然扩充区间后仍然不满足）。若不满足，递增枚举。
5、
可满足的含义： 对于一个字符x，假设它的下标为y，那么如果[left_bound,y)区间内所有的字符都可以在x的右侧找到，就称x字符是可满足的。
可满足的判定依据： 如果对于x左侧的任意一个字符，它对应的最大下标大于y，那么就判定x可满足。
6、如果x可满足，那么就遍历左侧的每一个字符，在字符对应的下标deque中执行pop_front，并对x本身对应的下标deque执行clear（需要判空操作避免内存引用错误以及deque的size下溢）。然后更新left_bound、cnt和答案字符串。 因为x已经被选定为答案中的字符，所以x以及x左侧的字符都可以从待去重字符串中删除，所以需要更新left_bound来控制待选字符串的范围。

代码：（leetcode执行通过）

string removeDuplicateLetters(string s)
    {
        string r;
        vector<deque<int> > ind(26, deque<int>());
        int n = s.size();
        for (int i = 0; i < n; i++)
            ind[s[i] - 'a'].push_back(i);
        int cnt = 0;
        for (int i = 0; i < 26; i++)
            if (!ind[i].empty())
                cnt++;
        int left_bound = 0;
        while (cnt--)
        {
            int j = 0;
        loop:
            while (ind[j].empty())
                j++;
            int index = ind[j].front();
            for (int i = index - 1; i >= left_bound; i--)
                if (!ind[s[i] - 'a'].empty() && ind[s[i] - 'a'].back() < index)
                {
                    j++;
                    goto loop;
                }
            for (int i = index - 1; i >= left_bound; i--)
                if (!ind[s[i] - 'a'].empty())
                    ind[s[i] - 'a'].pop_front();
            ind[j].clear();
            left_bound = index + 1;
            r.push_back(j + 'a');
        }
        return r;
    }

[TinyOrange98]

补充一下：将deque换成queue也是一样的。用goto语句是因为写起来方便，但是的确不是一种好的风格。

[labuladong]

👍

[TinyOrange98]

谢谢回复！
stack的思路很棒。但是我个人认为algo与ds，algo是第一位的（虽然这两者紧密交织，例如没有堆就没有堆排序，但是堆排序与朴素的选择排序在算法上完全一致），算法的设计应当不前向依赖任何未来知识。
所以我认为除非是非常简单的问题，否则一般情况下我们很难根据题目在没有明确算法的情况下就选取哪种ds。例如本题，我认为如果没有接触过单调栈相关的知识，是很难用这个特殊的数据结构解决这道题的。但这道题只是一个常规的贪心，它的解决方案并不强依赖于某种数据结构。

[SUN7700]

字典序：对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系

[bescks]

这个描述是我见过对字典序描述最简洁的

[wxharry]

leetcode 316 CPP版 参考自lc的题解。仅提供思路参考，完全没考虑复杂度。

class Solution {
public:
    string removeLetter(char ch, string s) {
        string r = "";
        for (char c: s) {
            if (c == ch) continue;
            r += c;
        }
        return r;
    }
    
    string removeDuplicateLetters(string s) {
        if (s == "") {
            return s;
        }
        vector<int> cnt(128, 0);
        for (char c: s) {
            ++ cnt[c];
        }
        int pos=0;
        for (int i=0; i < s.size(); ++i) {
            if(s[i] < s[pos]) {
                pos = i;
            }
            -- cnt[s[i]];
            if (!cnt[s[i]]) {
                break;
            }
        }
        return s[pos] + removeDuplicateLetters(removeLetter(s[pos], s.substr(pos+1, s.size() - pos)));
    }
};

[yudidian]

//js版本
var removeDuplicateLetters = function(s) {
  if (s.length === 1 || s.length === 0) {
    return s
  }
  const need = new Map()
  const count = new Map()
  const window = []
  let right = 0
  for (let i = 0; i < s.length; i++) {
    if (!count.has(s[i])) {
      count.set(s[i], 1)
    } else {
      count.set(s[i], count.get(s[i]) + 1)
    }
  }
  while (right < s.length) {
    const c = s[right]
    right++
    if (!need.has(c)) {
      if (window.length > 0) {
        while (window.length > 0 && window[window.length - 1].charCodeAt(0) > c.charCodeAt(0) && (count.get(window[window.length - 1]) > 1)) {
          const del = window.pop()
          need.delete(del)
          count.set(del, count.get(del) - 1)
        }
      }
      window.push(c)
      need.set(c, 1)
    } else {
      count.set(c, count.get(c) - 1)
    }
  }
  return window.join("")
};

[CarlLy7]

打卡，作为一名理科生，太喜欢这种层层逻辑推理的过程了

[outsmartchad]

C++ version:

class Solution {
public:
    string smallestSubsequence(string s) {
        int n = s.size();
        stack<char> sk;
        string res = "";
        vector<int> count(256, 0);
        vector<bool> seen(256, false);
        for(char c: s) count[c]++;
        for(int i=0; i<s.size(); i++){
            count[s[i]]--;
            if(seen[s[i]]) continue;
            while(!sk.empty()&&s[i]<sk.top()){
                if(count[sk.top()]==0) break;
                seen[sk.top()] =false;
                sk.pop();

            }
            sk.push(s[i]);
            seen[s[i]] = true;
        }
        while(!sk.empty()){
            res+=sk.top();
            sk.pop();
        }
        int l=0, r=res.size()-1;
        while(l<r){
            swap(res[l], res[r]);
            l++;
            r--;
        }
        return res;
    }
};