容器适配器
是一个封装了
序列容器
的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。将介绍 3 种容器适配器，分别是 stack、queue、priority_queue：
stack<T>
：是一个默认封装了 deque<T> 容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack<T> 模板定义在头文件 stack 中。
stack<T,Container=deque<T>>
模板类提供了 2 个参数，
通过指定第二个模板类型参数，我们可以使用出 deque 容器外的其它序列式容器，只要该容器支持 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数即可。序列式容器中同时包含这 5 个成员函数的，有 vector、deque 和 list 这 3 个容器。因此，stack 适配器的基础容器可以是它们 3 个中任何一个。例如，下面展示了如何定义一个使用 list 基础容器的 stack 适配器：
std::stack<std::string, std::list<int>> values;-
1、栈
1. 首先，明白一下栈常用的方法。具体的形象化表示可如下图。
stack 常用的一些成员函数
empty() //判断是否为空，为空返回true
size() //返回stack元素个数
top() //返回栈顶元素
push() //在栈顶添加元素
pop() //删除栈顶元素
2、栈的应用
-
判断字符串是否合法，利用先进后出进行模拟
【题目】字符串中只有字符'(‘和’)’。合法字符串需要括号可以配对。比如：
输入：”()”
输出：true
解释：()，()()，(())是合法的。)(，()(，(()是非法的。
#include <stack>
using namespace std;
bool checkvalid(string s){
if (s.empty())
return true;
if (s.size() % 2 != 0) // s.size()&1 == 1 为奇数
return false;
stack<char> sch;
int len = s.size();
for (int i = 0; i < len; i++){
char c = s[i];
if (c == '(')
sch.push(c);
if (c == ')'){
if (sch.empty())
return fasle;
sch.pop();
}
return sch.empty();
} 注意要考虑特殊情况。字符串为空；字符串只有 1 个或者奇数个。
上面的解法即是，用栈进行模拟，从左边往右边读单个字符，如果是左括号，则压入栈内，如果是右括号，先判断栈是否为空，如果为空则返回false，否则的话，删除栈顶元素（即两个括号相消）。
延申两个方向，1、上面的解法，我们可以看到时间复杂度是 O(n)，最差情况下，空间复杂度是O(n)。即每个元素都要进入栈内。
深度延申
，怎样降低空间复杂度。我们可以直接用计数器来判断。
栈中元素都相同时，实际上没有必要使用栈，只需要记录栈中元素个数。
#include <stack>
using namespace std;
bool checkvalid(string s){
if (s.empty())
return true;
if (s.size() % 2 != 0) // s.size()&1 == 1 为奇数
return false;
int coutStack = 0;
int len = s.size();
for (int i = 0; i < len; i++){
char c = s[i];
if (c == '(')
coutStack++;
if (c == ')'){
if (cooutStack < 0)
return fasle;
coutStack--;
}
return coutStack == 0;
} 上面这个空间复杂度会降成 O(1);
广度延申
，给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：
左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合；注意空字符串可被认为是有效字符串
//用栈，把三种情况都举例出来比较
bool isValid(string s) {
if (s.length() & 0x01) {
return false;
}
stack<char> t;
for (auto c : s) {
if (c == '{' || c == '[' || c == '(') {
t.push(c);
} else if (c == ')') {
if (t.empty() || t.top() != '(') {
return false;
}
t.pop();
} else if (c == '}') {
if (t.empty() || t.top() != '{') {
return false;
}
t.pop();
} else if (c == ']') {
if (t.empty() || t.top() != '[') {
return false;
}
t.pop();
} else {
return false;
}
}
return t.empty();
}//用 map 去存储。比较的时候，直接取值
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (char ch: s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
-
单调栈的应用
【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。
输入：[5, 2]
输出：[1, -1]
解释：因为元素 5 的右边离我最近且比我小的位置应该是 A[1]，最后一个元素 2 右边没有比 2 小的元素，所以应该输出 -1。
单调栈的意思就是，在栈内保持元素是单调的（单调增或者单调减）。
以 {1,2,4,9,4,0,5} 为例，进行模拟。
Step 1. 首先将 A[0] = 1 的下标 0 入栈。
Step 2. 将 A[1] = 2 的下标 1 入栈。满足单调栈。
Step 3. 将 A[2] = 4 的下标 2 入栈。满足单调栈。
Step 4. 将 A[3] = 9 的下标 3 入栈。满足单调栈。
Step 5. 将 A[4] = 4 的下标 4 入栈时，不满足单调性，需要将 A[3] = 9 从栈中弹出去。下标 4 将栈中下标 3 弹出栈，记录 A[3] 右边更小的是 index = 4。
Step 6. 将 A[5] = 0 的下标 5 入栈时，不满足单调性，需要将 A[4] = 4 从栈中弹出去。下标 5 将下标 4 弹出栈，记录 A[4] 右边更小的是 index = 5。A[5] = 0 会将栈中的下标 0, 1, 2 都弹出栈，因此也需要记录相应下标右边比其小的下标为 5，再将 A[5] = 0 的下标 5 放入栈中。
Step 7. 将 A[6] = 5 的下标 6 放入栈中。满足单调性。
Step 8. 此时，再也没有元素要入栈了，那么栈中的元素右边没有比其更小的元素。因此设置为 -1.
vector<int> finalResult(vector<int>& nums) {
int len = nums.size();
if(len == 0) return{};
stack<int> snums;
vector<int> result(len);
for (int i = 0; i < len; i++) {
const int x = nums[i];
while (!result.empty() && nums[snums.top()] > x) {
result[snums.top()] = i;
snums.pop();
}
snums.push(i);
}
while (!snums.empty()) {
result[snums.top()] = -1;
snums.pop();
}
return result;
}每个元素只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况可能会把所有的元素都入栈。相比较暴力搜索的O(n2)的时间复杂度，在数据量很大的情况下，效果还是很好的。
字典序最小的 k 个数的子序列
【题目】给定一个正整数数组和 k，要求依次取出 k 个数，输出其中数组的一个子序列，需要满足：1. 长度为 k；2.字典序最小。
输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的解：{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 字典序最小。
vector<int> finalResult(vector<int>& nums, int& k) {
int len = nums.size();
if (!len || k == 0) return {};
vector<int> result(k);
stack<int> stnum;
for (int i = 0; i < len; i++) {
const int x = nums[i];
int right = len - i;
while (!stnum.empty() && x < stnum.top() && (right + stnum.size()) < k) {
stnum.pop();
}
stnum.push(x);
}
while (stnum.size() > k) {
stnum.pop();
}
for (int i = k-1; i >= 0; i++) {
result[i] = stnum.top();
stnum.pop();
}
return result;
}
4. 边界问题：我们还是需要小心题目的边界。
Case 1：假设数组右边有一个最小的数，这个最小的数会把左边的数全部都消掉，然后递增栈里面就只剩下这 1 个数了。这跟题意有点不符合，题意需要的是找到 k = 2 个出来。
解决办法：不过你可以想一想，是不是可以控制一下消去的数目。当剩下的数字个数与栈中的元素刚好能凑够 k 个数时，就不能再消除了，
Case 2：如果数组是一个升序的数组，那么此时所有的元素都会被压栈。栈中的数目有可能远远超出 k 个。
解决办法：只需要把栈中的多出来的数字弹出来即可。