155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
提示：
-
\(-2^{31}\) <= val <= \(2^{31}\) - 1
-
pop、top 和 getMin 操作总是在 非空栈 上调用
-
push, pop, top, and getMin最多被调用 \(3 * 10^4\) 次
-
思路解析
因为会不断的入栈和出栈，那就要保证，不论入栈还是出栈，我时刻知道，到栈中当前位置的最小值是谁。
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
对于上述输入，-2入栈时，最小值是-2，0入栈是，最小值是-2，-3入栈是最小值是-3
也就是我需要两个栈，一个栈用于存储元素，完成元素的push和pop操作；一个栈用于存储当前最小值，如果最小值更新就存入最小栈。
class MinStack {
public:
MinStack() {
}
void push(int val) {
if (val <= getMin()) {
minStack.emplace(val);
}
valStack.emplace(val);
}
void pop() {
if (valStack.empty()) {
return;
}
int ret = valStack.top();
valStack.pop();
if (ret == getMin()) {
minStack.pop();
}
}
int top() {
return valStack.top();
}
int getMin() {
if (minStack.empty()) {
return INT_MAX;
}
return minStack.top();
}
private:
stack<int> valStack;
stack<int> minStack;
};
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
-
左括号必须用相同类型的右括号闭合。
-
左括号必须以正确的顺序闭合。
-
每个右括号都有一个对应的相同类型的左括号。
-
思路解析
将匹配项做一个map单独存储，这样子有更好的扩展性。
遇到左括号就入栈，遇到右括号，判断是否与栈顶元素配对，配上就出栈，否则就返回false。
class Solution {
public:
bool isValid(string s) {
stack<char> bracketsStack;
for (auto &iter : s) {
// 遇到左括号就入栈，遇到右括号，判断栈顶是否为其对应的左括号，如果是则出栈
if (typeMap.count(iter) != 0) {
bracketsStack.emplace(iter);
} else {
if (bracketsStack.empty() || iter != typeMap[bracketsStack.top()]) {
return false;
}
bracketsStack.pop();
}
}
if (bracketsStack.empty()) {
return true;
}
return false;
}
private:
unordered_map<char, char> typeMap = {
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
};
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入："abbaca"
输出："ca"
输入："abbbaca"
输出："abaca"
-
思路解析
string提供了两个操作
- front：访问第一个字符
- back：查询最后一个字符
- pop_back：弹出尾巴字符，实现：length - 1即可
- push_back：插入元素
string removeDuplicates(string s) {
string res;
for (auto &iter : s) {
if (!res.empty() && iter == res.back()) {
res.pop_back();
} else {
res.push_back(iter);
}
}
return res;
}
1209. 删除字符串中的所有相邻重复项 II
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
-
思路解析
遍历到某个字符的时候，判断当前字符与栈顶字符是否相同
- 如果不同，则直接入栈并开始计数
- 如果相同，则判断当前栈顶元素累积了多少个该元素，如果累积的个数小于k-1，则继续累积，如果累积到了k-1个，当前又相同了，那么栈顶元素就可以弹出了。
string removeDuplicates(string s, int k) {
stack<std::pair<char, int>> pairStack; // 每个元素存储当前的元素及有几个连续的值
for (size_t i = 0; i < s.length(); i++) {
if (!pairStack.empty() && pairStack.top().first == s[i]) {
// 此时，看一下栈中是否已经有k-1个s[i]相同的元素，如果有，则pop出这k-1个，如果没有，则push进去
if (pairStack.top().second == k - 1) {
pairStack.pop();
} else {
pairStack.top().second++;
}
} else {
pairStack.emplace(std::pair<char, int>(s[i], 1));
}
}
string res;
while(!pairStack.empty()) {
while (pairStack.top().second-- > 0) {
res += pairStack.top().first;
}
pairStack.pop();
}
reverse(res.begin(), res.end());
return res;
}
删除字符串中出现次数 >= 2 次的相邻字符
第二次出现的时候，说明出现次数大于2了，这时候就可以删除了，同时跳过s中后续与当前字符相同的元素即可。
string removeDuplicates(string s, int k) {
string res; // 每个元素存储当前的元素及有几个连续的值
for (size_t i = 0; i < s.length(); ) {
if (!res.empty() && res.back() == s[i]) {
// 此时，说明已经出现过的字符第二次出现了
char currChar = s[i];
while(s[i] == currChar) {
// 跳过s中其他相同的字符
i++;
}
res.pop_back();
} else {
res.push_back(s[i]);
i++;
}
}
return res;
}
剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
class CQueue {
public:
CQueue() {
}
void appendTail(int value) {
stackIn.emplace(value);
}
int deleteHead() {
if (stackOut.empty()) {
while (!stackIn.empty()) {
stackOut.emplace(stackIn.top());
stackIn.pop();
}
}
if (stackOut.empty()) {
return -1;
}
auto ret = stackOut.top();
stackOut.pop();
return ret;
}
private:
stack<int> stackOut; // 输出栈，元素按照输入顺序的栈
stack<int> stackIn; // 输入元素存放栈，与输入顺序相反的栈
};
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
-
思路解析
假设窗口为[left, right]，那么只要nums[i]比nums[j]小，则nums[i]就不纳入考虑范围。所以，当right进入窗口的时候，前面比nums[right]小的元素统统可以移除考虑范围了；这样子，留下的元素是从大到小有序的。
因为我们要移除比当前元素小的元素，也要获取最大的元素作为当前窗口最大值，因此，可以使用双端队列来实现。
// 移除比当前元素小的所有元素,只留下比当前元素大的元素
while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {
dQ.pop_back();
}
// 获取当前窗口最大值,放入结果中
resVec.emplace_back(nums[dQ.front()]);
// 如果最大值应该要移除了，则移除
if (dQ.front() + k <= i) {
dQ.pop_front();
}
完整的实现代码如下：
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dQ;
for (size_t i = 0; i < k; i++) {
// 当前队列中仅保留比当前元素大的元素的位置,队列中下标对应的元素由大到小
while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {
dQ.pop_back();
}
dQ.emplace_back(i);
}
vector<int> resVec = {nums[dQ.front()]};
for (size_t i = k; i < nums.size(); i++) {
// 当前队列中仅保留比当前元素大的元素的位置
while (!dQ.empty() && nums[i] >= nums[dQ.back()]) {
dQ.pop_back();
}
dQ.emplace_back(i);
if (dQ.front() <= i - k) {
dQ.pop_front();
}
resVec.emplace_back(nums[dQ.front()]);
}
return resVec;
}
需要完整版练习笔记，可关注公众号后台私信~~