目录
基本概念
栈
先进后出，后进先出
对称
队列、双端队列
先进先出，后进后出
顺序
155.最小栈
题目描述
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
题目实现
class MinStack {
stack<int> stackA;
stack<int> stackB;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
stackA.push(x);
if (stackB.size() == 0) {
stackB.push(x);
}else{
int top = stackB.top();
top < x ? stackB.push(top) : stackB.push(x);
}
}
void pop() {
if (stackA.size() == 0)return;
stackA.pop();
stackB.pop();
}
int top() {
return stackA.top();
}
int getMin() {
return stackB.top();
}
};
20.有效的括号
题目描述
_20_有效的括号 -https://leetcode-cn.com/problems/valid-parentheses/
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
题目实现
class Solution {
public:
bool isValid(string s) {
int n = (int)s.size();
if (n & 1 == 1) return false;
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (char ch: s) {
//pairs.count，判断key是否存在，存在返回1，不存在返回0
if (pairs.count(ch)) {//如果是右半边出栈
//右半边时，栈为空或栈顶不能配对，不可能是有效的括号
if (stk.empty() || stk.top() != pairs[ch]) return false;
stk.pop();
}else {//如果是左半边入栈
stk.push(ch);
}
}
return stk.empty();
}
};
232.用栈实现队列
题目描述
232. 用栈实现队列- https://leetcode-cn.com/problems/implement-queue-using-stacks/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
题目实现
class MyQueue {
stack<int> * inStack;
stack<int> * outStack;
public:
/** Initialize your data structure here. */
MyQueue() {
this->inStack = new stack<int>();
this->outStack = new stack<int>();
}
~MyQueue(){
delete inStack;
inStack = nullptr;
delete outStack;
outStack = nullptr;
}
/** Push element x to the back of queue. */
void push(int x) {
this->inStack->push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if (outStack->size() == 0) {
while (inStack->size()!=0) {
outStack->push(inStack->top());
inStack->pop();
}
}
int val = this->outStack->top();
this->outStack->pop();
return val;
}
/** Get the front element. */
int peek() {
if (outStack->size() == 0) {
while (inStack->size()!=0) {
outStack->push(inStack->top());
inStack->pop();
}
}
return outStack->top();
}
/** Returns whether the queue is empty. */
bool empty() {
return outStack->size() == 0 && inStack->size() == 0;
}
};
239.滑动窗口最大值
题目描述
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
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
实现方式一
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//返回一个空数组
if (nums.size() == 0 || k < 1) return vector<int>(0);
//返回nums
if (k == 1) return nums;
//创建一个存放滑动窗口最大值的数组
int length = (int)nums.size()-k+1;
vector<int> maxes(length);//6 - 3 +1
int maxIdx = -1;
for (int i = 0; i<length; i++) {
if (maxIdx<i) {
maxIdx = maxIdxFromK(nums, i, i+k-1);
}else{
if(nums[i+k-1] > nums[maxIdx]){
maxIdx = i+k-1;
}
}
maxes[i] = nums[maxIdx];
cout<<maxIdx<<endl;
}
return maxes;
}
int maxIdxFromK(vector<int>& nums,int star,int end){
int maxIdx = star;
for (int i = star+1; i<=end; i++) {
if (nums[i] > nums[maxIdx]) {
maxIdx = i;
}
}
return maxIdx;
}
};
实现方式二：双端队列
//时间复杂度O(n),空间复杂度O(n-k)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//返回一个空数组
if (nums.size() == 0 || k < 1) return vector<int>(0);
//返回nums
if (k == 1) return nums;
//创建一个存放滑动窗口最大值的数组
vector<int> maxes(nums.size()-k+1);
//创建一个双端队列
deque<int> intDeque;
for (int ri = 0; ri<nums.size(); ri++) {
// 只要nums[队尾] <= nums[i]，就删除队尾
while (!intDeque.empty() && nums[ri] >= nums[intDeque.back()]) {
intDeque.pop_back();
}
// 将i加到队尾
intDeque.push_back(ri);
// 检查窗口的索引是否合法
int li = ri - k + 1;
if (li < 0) continue;
// 检查队头的合法性
if (intDeque.front() < li) {
// 队头不合法（失效，不在滑动窗口索引范围内）
intDeque.pop_front();
}
// 设置窗口的最大值
maxes[li] = nums[intDeque.front()];
}
return maxes;
}
};
行者常至，为者常成！