LeetCode题解(七) - Remove-Duplicate-Letters
题目难度：Hard
题目地址：No.316 Remove Duplicate Letters
题目描述：
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: "bcabc"
Output: "abc"
Example 2:
Input: "cbacdcbc"
Output: "acdb"
本题是一道利用贪心算法，根据输入字符串，通过去除其中重复的字符，最终要求得到所有的可能输出中，字典排序最小的，不存在任何重复字符的目标串。
题目思路：
-
贪心算法题目的解题重点在于贪心准则的选取，以及字符串生成策略的决定。首先这道题的突破口在于选取最小字符的位置，由此判断其两侧字符的保留与否。此处需要借助堆栈
Stack数据结构，每次扫描字符串，将未入栈的字符入栈，入栈前需要与栈顶元素进行大小比较，若栈顶元素大于其则栈顶会被弹出，以保证最小字典序。 -
上述思路的实现，需要使用到两个辅助数组：一个是负责记录字符出现次数的数组
count，另一个是入栈标记数组visited。每次扫描字符之时，去除其一次count，同时已在栈内者不做扫描，不在栈内者进行栈顶大小比较，小于top者进行替换，栈顶被弹出(循环操作)，但是仍有机会进行入栈操作，其visited值设为true。 -
最终得到的栈内字符顺序必定是倒序，每个小元素都逐渐被压至栈底。
代码实现：
class Solution {
public:
string removeDuplicateLetters(string s) {
stack<char> store;
string result = "";
int visited[26] = {0}, count[26] = {0};
for(int i=0; i<s.size(); i++)
count[s[i] - 'a']++;
for(int i=0; i<s.size(); i++){
int index = s[i] - 'a';
count[index]--;
if(visited[index]) continue;
while(!store.empty() && s[i] < store.top() && count[store.top() - 'a']>0){
visited[store.top() - 'a'] = false;
store.pop();
}
visited[index] = true;
store.push(s[i]);
}
while(!store.empty()){
result = store.top() + result;
store.pop();
}
return result;
}
};
运行结果：
