根据单调栈的特性去解决一些问题，结合leetcode
利用单调栈的特性去除重复字符
去除重复字符
图解
文字描述：
第 1 步：读到 c，入栈，此时栈中元素 [c]；
第 2 步：读到 b，b 比之前 a 小，c 在以后还会出现，因此 c 出栈，b 入栈，此时栈中元素 [b]；
第 3 步：读到 a，a 比之前 b 小，b 在以后还会出现，因此 b 出栈，a 入栈，此时栈中元素 [a]；
第 4 步：读到 c，c 比之前 a 大，直接让 c 入栈，此时栈中元素 [a, c]；
第 5 步：读到 d，d 比之前 d 大，直接让 d 入栈，此时栈中元素 [a, c, d]；
第 6 步：读到 c，这里要注意：此时栈中已经有 c 了，此时栈中元素构成的字符顺序就是最小的字典序，不可能舍弃之前的 c，而用现在的读到的 c，因此这个 c 不需要，直接跳过；
第 7 步：读到 b，b 比之前的 d 小，但是，后面不会再出现 d 了，因此 b 就应该放在这个位置，因此让 b 入栈，此时栈中元素 [a, c, d, b]；
第 8 步：读到 c，同第 6 步，这个 c 我们不需要。
上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
string removeDuplicateLetters(string s) {
size_t size = s.size();
if(size < 2){
return s;
}
bool used[26];
for(bool &i:used){
i = false;
}
int lastAppearIndex[26];
for(int i = 0; i < size;i++){
lastAppearIndex[s[i] - 'a'] = i;
}
stack<char> st;
for(int i = 0;i < size;i++){
if(used[s[i] - 'a']){
continue;
}
while(!st.empty() && st.top() > s[i] && lastAppearIndex[st.top() - 'a'] >= i){
char top = st.top();
st.pop();
used[top - 'a'] = false;
}
st.push(s[i]);
used[s[i] - 'a'] = true;
}
string res;
while(!st.empty()){
res += st.top();
st.pop();
}
reverse(res.begin(),res.end());
return res;
}
};
|
拼接最大数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> res(k, 0);
int n = nums1.size(), m = nums2.size();
for (int s=max(0, k-m); s<=min(k, n); s++){
vector<int> temp;
int i = 0, j = 0;
vector<int> temp1 = maxKsequence(nums1, s);
vector<int> temp2 = maxKsequence(nums2, k-s);
auto iter1 = temp1.begin(), iter2 = temp2.begin();
while (iter1 != temp1.end() || iter2 != temp2.end()){
temp.push_back(lexicographical_compare(iter1, temp1.end(), iter2, temp2.end()) ? *iter2++ : *iter1++);
}
res = lexicographical_compare(res.begin(), res.end(), temp.begin(), temp.end()) ? temp : res;
}
return res;
}
vector<int> maxKsequence(vector<int> v, int k){
int n = v.size();
if (n <= k)
return v;
vector<int> res;
int pop = n-k;
for (int i=0; i<n; i++){
while(!res.empty() && v[i]>res.back() && pop-->0)
res.pop_back();
res.push_back(v[i]);
}
res.resize(k);
return res;
}
};
|
这个时候我就在想，vector的功能不是和stack类型吗？甚至可以说一样
那么为什么设计C++语言的大佬，要设计除stack呢？
std::vector 是容器，而 std::stack 是容器适配器。
std::stack只提供和堆栈相关的接口，其中主要是 push()、emplace()、pop()、top()和empty()。使用 std::stack时只需关心这些接口，而非内在用了哪个具体容器。改变容器类型也不需要修改调用方的代码。这个设计应该可说是乎合 SOLID 中的 I ──接口隔离原则（interface segregation principle）。
std::stack 可适配的标准容器有 std::vector、std::list、std::deque，而 std::deque 是缺省的，因为它提供 O(1) 的push_back()，而 std::vector::push_back()是均摊（amortized） O(1)。
移掉K位字数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
string removeKdigits(string num, int k)
{
string result;
for (int i = 0; i < num.size(); i++)
{
while (result.size() && k&&result.back() > num[i])
{
result.pop_back();
k--;
}
if (result.size() == 0 && num[i] == '0')
continue;
result+=num[i];
}
while (k > 0 && !result.empty())
{
result.pop_back();
k--;
}
return result == "" ? "0" : result;
}
};
|
这个我个人感觉主要是在如何去处理0，毕竟0很特殊
不同字符的最小子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
string smallestSubsequence(string s) {
int n = s.size();
if(n < 2){
return s;
}
bool used[26];
for(int i = 0;i < 26;++i){
used[i] = false;
}
int lastword[26];
for(int i = 0;i < n;++i){
lastword[s[i] - 'a'] = i;
}
stack<char> able;
for(int i = 0;i < n;++i){
if(used[s[i] - 'a']){
continue;
}
while(!able.empty() && s[i] < able.top() && lastword[able.top() - 'a'] >= i){
used[able.top() - 'a'] = false;
able.pop();
}
able.push(s[i]);
used[s[i] - 'a'] = true;
}
string result;
while(!able.empty()){
result.push_back(able.top());
able.pop();
}
reverse(result.begin(),result.end());
return result;
}
};
|
这题本质就是本文的第一题，亲自手打，然后能够得到结果，确实挺不错的。
这些题目我感觉只有第二题是比较难的，一是不好去理解，二是利用归并思想