去除重复字母
- leetcode 316 ，Hard
**
题目的要求总结出来有三点： 要求一、要去重。 要求二、去重字符串中的字符顺序不能打乱
s中字符出现的相对顺序。 要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。
我们先暂时忽略要求三，先来来实现一下要求一和要求二
1、去重。一般用set，但提干可以保证均为小写字符，所以此处用一个简单的bool数组即可。
2、相对 顺序的保持。按顺序去重是可以保证相对顺序的。
bool map[256];for(int i=0;i<256;++i){map[i]=false;}vector<int> ret;for(auto c:s){if(map[c]==true){continue;}ret.push(c);map[c]=true;}return ret;
如果来满足要求三，保证字典序，需要做些什么修改？
最经典的技巧是使用单调栈来保证最后得到一个递增的字符串。
string removeDuplicateLetters(string s) {
bool map[256];
stack<char> stk;
for(int i=0;i<256;++i){
map[i]=false;
}
//默写单调栈模板
for(auto c:s){
if(map[c]==true){
continue;
}
while(stk.empty()==false&&c<stk.top()){
map[stk.top()]=false;
stk.pop();
}
stk.push(c);
map[c]=true;
}
//整理返回值
string ret;
while(stk.empty()==false){
ret+=stk.top();
stk.pop();
}
reverse(ret.begin(),ret.end());
return ret;
}
但是，如果我改一下输入，假设s = "bcac"，按照刚才的算法逻辑，返回的结果是"ac"，而正确答案应该是"bac"，分析一下这是怎么回事？
很容易发现，因为s中只有唯一一个'b'，即便字符'a'的字典序比字符'b'要小，字符'b'也不应该被 pop 出去。
那问题出在哪里？
我们的算法在stk.top() > c时才会 pop 元素，其实这时候应该分两种情况：**
情况一、如果
stk.top()这个字符之后还会出现，那么可以把它 pop 出去，反正后面还有嘛，后面再 push 到栈里，刚好符合字典序的要求。 情况二、如果stk.top()这个字符之后不会出现了，前面也说了栈中不会存在重复的元素，那么就不能把它 pop 出去，否则你就永远失去了这个字符。
我们用了一个计数器count，当字典序较小的字符试图「挤掉」栈顶元素的时候，在count中检查栈顶元素是否是唯一的，只有当后面还存在栈顶元素的时候才能挤掉，否则不能挤掉。
string removeDuplicateLetters(string s) {
vector<bool> map(26,false);
stack<char> stk;
vector<int> count(26,0);
for(auto c:s){
count[c-'a']++;
}
//默写单调栈模板
for(auto c:s){
count[c-'a']--;
if(map[c-'a']==true){
continue;
}
while(stk.empty()==false&&c<stk.top()){
//后面没有的时候不能弹出
if(count[stk.top()-'a']==0){
break;
}
map[stk.top()-'a']=false;
stk.pop();
}
stk.push(c);
map[c-'a']=true;
}
//整理返回值
string ret;
while(stk.empty()==false){
ret+=stk.top();
stk.pop();
}
reverse(ret.begin(),ret.end());
return ret;
}
滑动窗口最大值
- leetcode 239 ，Hard
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
一、搭建解题框架
一个普通的队列一定有这两个操作：
class Queue {
// enqueue 操作，在队尾加入元素 n
void push(int n);
// deque 操作，删除队头元素
void pop();
}
一个「单调队列」的操作也差不多：
class MonotonicQueue {
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
}
当然，这几个 API 的实现方法肯定跟一般的 Queue 不一样，不过我们暂且不管，而且认为这几个操作的时间复杂度都是 O(1)，先把这道「滑动窗口」问题的解答框架搭出来：
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ret;
MonotonicQueue window;
for(int i=0;i<nums.size();++i){
//先把窗口的前 k - 1 填满
if(i<k-1){
window.push(nums[i]);
}else{
// 窗口开始向前滑动
// 移入新元素
window.push(nums[i]);
// 将当前窗口中的最大元素记入结果
ret.emplace_back(window.max());
// 移出最后的元素
window.pop(nums[i-k+1]);
}
}
return ret;
}
二、实现单调队列
观察滑动窗口的过程就能发现，实现「单调队列」必须使用一种数据结构支持在头部和尾部进行插入和删除，很明显deque是满足这个条件的。
class MonotonicQueue {
public:
// 在队尾添加元素 n
void push(int n);
// 返回当前队列中的最大值
int max();
// 队头元素如果是 n，删除它
void pop(int n);
private:
deque<int> que;
};
「单调队列」的核心思路和「单调栈」类似，push方法依然在队尾添加元素，因为要获得最大的元素，所以希望前面的都比自己大：
void push(int n){
while(que.empty()==false&&n>que.back()){
que.pop_back();
}
que.push_back(n);
}
如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序，因此我们的max方法可以可以这样写：
int max(){
return que.front();
}
pop方法在队头删除元素n，也很好写：
void pop(int n){
if(que.empty()==false&&n==que.front()){
que.pop_front();
}
}
总的如下：
class MonotonicQueue{
public:
void push(int n){
while(que.empty()==false&&n>que.back()){
que.pop_back();
}
que.push_back(n);
}
void pop(int n){
if(que.empty()==false&&n==que.front()){
que.pop_front();
}
}
int max(){
return que.front();
}
private:
deque<int> que;
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ret;
MonotonicQueue window;
for(int i=0;i<nums.size();++i){
if(i<k-1){
window.push(nums[i]);
}else{
window.push(nums[i]);
ret.emplace_back(window.max());
window.pop(nums[i-k+1]);
}
}
return ret;
}
单独看
push操作的复杂度确实不是O(1)，但是算法整体的复杂度依然是O(N)线性时间。要这样想，nums中的每个元素最多被push_back和pop_back一次，没有任何多余操作，所以整体的复杂度还是O(N)。 空间复杂度就很简单了，就是窗口的大小O(k)。
若有收获，就点个赞吧
0 人点赞
