- 155. 最小栈
- 思路解析
- 20. 有效的括号
- 思路解析
- 1047. 删除字符串中的所有相邻重复项
- 思路解析
- 1209. 删除字符串中的所有相邻重复项 II
- 思路解析
- 删除字符串中出现次数 >= 2 次的相邻字符
- 剑指 Offer 09. 用两个栈实现队列
- 239. 滑动窗口最大值
- 思路解析
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 valStack; stack minStack;}; 20. 有效的括号
给定一个只包括 "("，")"，"{"，"}"，"["，"]" 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
思路解析
将匹配项做一个map单独存储，这样子有更好的扩展性。
遇到左括号就入栈，遇到右括号，判断是否与栈顶元素配对，配上就出栈，否则就返回false。
class Solution {public: bool isValid(string s) { stack 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 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> 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(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 stackOut; // 输出栈，元素按照输入顺序的栈 stack 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 maxSlidingWindow(vector& nums, int k) { deque 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 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;} 需要完整版练习笔记，可关注公众号后台私信~~
