发布工程信息的网站有哪些_阿里云邮箱企业邮箱_公司网站seo公司_有免费推广平台

最小栈 题解

一、题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。

• void push(int val) 将元素 val 推入堆栈。

• void pop() 删除堆栈顶部的元素。

• int top() 获取堆栈顶部的元素。

• int getMin() 获取堆栈中的最小元素。

二、解题思路

为了在常数时间内检索到最小元素，我们可以使用两个栈：一个主栈 _st 用于存储所有元素，另一个辅助栈 _minst 用于存储当前的最小元素。

1. push(int val) 操作：

   • 将元素 val 压入主栈 _st。

   • 检查辅助栈 _minst 是否为空，或者 val 是否小于等于辅助栈 _minst 的栈顶元素。如果是，则将 val 也压入辅助栈 _minst。这样可以保证辅助栈 _minst 的栈顶元素始终是当前主栈 _st 中的最小元素。

2. pop() 操作：

   • 检查主栈 _st 的栈顶元素是否等于辅助栈 _minst 的栈顶元素。如果相等，说明即将从主栈 _st 中弹出的元素是当前的最小元素，因此需要将辅助栈 _minst 的栈顶元素也弹出。

   • 弹出主栈 _st 的栈顶元素。

3. top() 操作：

   • 直接返回主栈 _st 的栈顶元素。

4. getMin() 操作：

   • 直接返回辅助栈 _minst 的栈顶元素，因为辅助栈 _minst 的栈顶元素始终是当前主栈 _st 中的最小元素

三、代码 

#include <stack>class MinStack {
public:// 主栈，存储所有元素std::stack<int> _st;// 辅助栈，存储当前的最小元素std::stack<int> _minst;MinStack() {}void push(int val) {_st.push(val);if (_minst.empty() || val <= _minst.top()) {_minst.push(val);}}void pop() {if (_st.top() == _minst.top()) {_minst.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
};

四、复杂度分析

1. 时间复杂度：

   • push(int val) 操作：每次压入元素时，主栈和辅助栈的操作时间复杂度均为 \(O(1)\)，所以总的时间复杂度为 \(O(1)\)。
   • pop() 操作：每次弹出元素时，主栈和辅助栈的操作时间复杂度均为 \(O(1)\)，所以总的时间复杂度为 \(O(1)\)。
   • top() 操作：获取主栈栈顶元素的时间复杂度为 \(O(1)\)。
   • getMin() 操作：获取辅助栈栈顶元素的时间复杂度为 \(O(1)\)。

2. 空间复杂度：

   • 主栈 _st 存储所有元素，在最坏情况下，需要存储 n 个元素，空复杂度为 \(O(n)\)。
   • 辅助栈 _minst 在最坏情况下，也需要存储 n 个元素（例如元素依次递减入栈），空间复杂度为 \(O(n)\)。所以总的空间复杂度为 \(O(n)\)，其中 n 是栈中元素的个数。

 栈的压入、弹出序列

 

一、题目描述

• 给定两个整数序列 pushV 和 popV，pushV 表示栈的压入顺序，需要判断 popV 是否为该栈可能的弹出顺序。

• 约束条件为：两个序列长度相等且在 0 到 1000 之间，pushV 中的元素取值范围是 -1000 到 1000 且所有元素互不相同。

二、解题思路

1. 辅助栈模拟：利用一个辅助栈 s 来模拟栈的操作。通过遍历 pushV 和 popV 序列，将 pushV 中的元素依次压入辅助栈，在合适的时机尝试弹出栈顶元素与 popV 中的元素进行匹配。

2. 双指针遍历：使用两个指针，i 用于遍历 popV，j 用于遍历 pushV。

3. 入栈操作：在遍历 popV 时，只要栈为空或者栈顶元素不等于当前 popV[i]，就持续将 pushV[j] 压入栈中并移动 j 指针，直到满足栈顶元素等于 popV[i] 或者 j 到达 pushV 的末尾。

4. 出栈匹配：当栈顶元素等于 popV[i] 时，弹出栈顶元素，表示该元素成功匹配弹出顺序；如果栈顶元素始终不等于 popV[i]，则说明 popV 不是合法的弹出顺序，返回 false。

5. 最终判断：如果遍历完 popV 后，所有元素都能成功匹配弹出顺序，则返回 true。

三、代码

#include <vector>
#include <stack>class Solution {
public:bool IsPopOrder(std::vector<int> pushV, std::vector<int> popV) {int n = pushV.size();// 辅助栈std::stack<int> s;// 遍历入栈的下标int j = 0;// 遍历出栈的数组for (int i = 0; i < n; i++) {// 入栈：栈为空或者栈顶不等于出栈数组while (j < n && (s.empty() || s.top() != popV[i])) {s.push(pushV[j]);j++;}// 栈顶等于出栈数组if (s.top() == popV[i]) {s.pop();} // 不匹配序列else {return false;}}return true;}
};

1. 初始化变量：获取 pushV 的长度 n，初始化辅助栈 s 和遍历 pushV 的指针 j。
2. 遍历 popV：在 for 循环中遍历 popV，对于每个 popV[i]，通过 while 循环将 pushV 中的元素压入栈，直到栈顶元素等于 popV[i] 或者 pushV 遍历完。
3. 匹配判断：如果栈顶元素等于 popV[i]，弹出栈顶元素；否则，说明 popV 不是合法弹出顺序，返回 false。
4. 返回结果：遍历完 popV 后，若所有元素都匹配，返回 true。

四、复杂度分析

1. 时间复杂度：由于每个元素最多入栈和出栈一次，所以时间复杂度为 \(O(n)\)，其中 n 是序列的长度。
2. 空间复杂度：在最坏情况下，辅助栈需要存储所有的元素，所以空间复杂度为 \(O(n)\)。

 

用队列实现栈

一、题目要求

题目要求使用队列来实现栈的功能，需要实现栈的基本操作，包括push（入栈）、pop（出栈）、top（获取栈顶元素）和empty（判断栈是否为空）。

二、解题思路

1. 数据结构选择：使用两个队列q1和q2来模拟栈。队列的特点是先进先出（FIFO），而栈的特点是后进先出（LIFO），通过巧妙地操作两个队列来实现栈的特性。

2. push操作：

   • 每次有新元素x要入栈时，先将其放入q2队列。

   • 然后把q1队列中所有元素依次取出并放入q2队列，这样q2队列的顺序就变为了栈的顺序（后进先出）。

   • 最后交换q1和q2，使得q1成为存储栈元素的队列，q2为空，方便下一次push操作。这样保证每次新元素都在q1的队首，即栈顶位置。

3. pop操作：

   • 直接取出q1的队首元素，因为经过push操作后，q1的队首元素就是栈顶元素。

   • 取出后将其从q1中删除，实现栈的出栈操作。

4. top操作：

   • 直接返回q1的队首元素，该元素即为栈顶元素。

5. empty操作：

   • 通过判断q1是否为空来确定栈是否为空。如果q1为空，说明栈中没有元素，返回true；否则返回false。

三、代码实现

#include <queue>class MyStack {
public:MyStack() {}void push(int x) {q2.push(x);while (!q1.empty()) {q2.push(q1.front());q1.pop();} std::swap(q1, q2); }int pop() {int r = q1.front();q1.pop();return r;}int top() {int r = q1.front();return r;}bool empty() {return q1.empty();}
private:std::queue<int> q1, q2;
};

1. 构造函数MyStack()：目前构造函数为空，可用于初始化一些必要的状态，但在这个实现中暂时没有需要初始化的特殊内容。

2. push(int x)函数：完成元素入栈操作，如上述思路中所述，通过两个队列的操作和交换来保证新元素在栈顶位置。

3. pop()函数：返回并删除栈顶元素，即q1的队首元素。

4. top()函数：返回栈顶元素，也就是q1的队首元素。

5. empty()函数：判断栈是否为空，通过检查q1是否为空来实现。

四、复杂度分析

1. 时间复杂度：

   • push操作：每次push操作中，将q1的元素转移到q2的过程，时间复杂度为\(O(n)\)，其中n是当前栈中元素的数量（因为需要遍历q1中的所有元素）。其他操作pop、top和empty的时间复杂度均为\(O(1)\)，因为它们只涉及对队列的简单操作（取队首、判断是否为空）。

2. 空间复杂度：

   • 总共使用了两个队列q1和q2，在最坏情况下，两个队列中存储的元素总数与栈中元素数量相同，所以空间复杂度为O(n)，n为栈中元素的最大数量。

 

栈实现队列

一、题目要求

使用两个栈来实现一个队列的功能，需要实现队列的基本操作，包括 push（入队）、pop（出队）、peek（查看队首元素）和 empty（判断队列是否为空）。

二、解题思路

1. 数据结构选择：选择两个栈 a 和 b 来模拟队列的行为。栈的特点是后进先出（LIFO），而队列的特点是先进先出（FIFO），通过巧妙地操作这两个栈来实现队列的特性。

2. push 操作：

   • 每次有新元素 x 要入队时，直接将其压入栈 a 中。因为栈 a 用于存储新加入的元素，所以新元素入栈的操作非常简单直接。

3. pop 操作：

   • 先调用 peek 函数获取队首元素（即最早入队的元素）。这是因为在 peek 函数中会确保队首元素在栈 b 的栈顶。

   • 然后从栈 b 中弹出该元素，实现出队操作。这样就保证了先进先出的队列特性。

4. peek 操作：

   • 首先检查栈 b 是否为空。如果栈 b 不为空，说明队首元素就在栈 b 的栈顶，直接返回栈 b 的栈顶元素。

   • 如果栈 b 为空且栈 a 也为空，说明队列中没有元素，返回 -1。

   • 如果栈 b 为空但栈 a 不为空，需要将栈 a 中的所有元素依次弹出并压入栈 b 中。这样做的目的是将栈 a 中最早入队的元素转移到栈 b 的栈顶，以符合队列先进先出的特性。最后返回栈 b 的栈顶元素，即队首元素。

5. empty 操作：

   • 判断队列是否为空，只需检查栈 a 和栈 b 是否都为空。如果两个栈都为空，说明队列中没有元素，返回 true；否则返回 false。

三、代码实现

#include <stack>class MyQueue {
public:MyQueue() {}void push(int x) {a.push(x);}int pop() {int peek = this->peek();b.pop();return peek;}int peek() {if (!b.empty()) {return b.top();}if (a.empty()) {return -1;}while (!a.empty()) {b.push(a.top());a.pop();}int ret = b.top();return ret;}bool empty() {return a.empty() && b.empty();}private:std::stack<int> a, b;
};

1. 构造函数 MyQueue()：目前构造函数为空，可用于初始化一些必要的状态，但在这个实现中暂时没有需要初始化的特殊内容。

2. push(int x) 函数：将新元素 x 压入栈 a 中，实现入队操作。

3. pop() 函数：先调用 peek 函数获取队首元素，然后从栈 b 中弹出该元素，返回队首元素，实现出队操作。

4. peek() 函数：按照上述思路，检查栈 b 和栈 a 的状态，将元素在两个栈之间转移，最终返回队首元素。

5. empty() 函数：判断栈 a 和栈 b 是否都为空，返回相应的结果，以确定队列是否为空。

四、复杂度分析

1. 时间复杂度：

   • push 操作：时间复杂度为 \(O(1)\)，因为只是将元素压入栈 a，操作简单直接。

   • pop 操作：时间复杂度在平均情况下为 \(O(1)\)，但在某些情况下（当栈 b 为空且需要将栈 a 的元素转移到栈 b 时），时间复杂度为 \(O(n)\)，其中 n 是栈 a 中元素的数量。

   • peek 操作：时间复杂度在平均情况下为 \(O(1)\)，但在某些情况下（当栈 b 为空且需要将栈 a 的元素转移到栈 b 时），时间复杂度为 \(O(n)\)，其中 n 是栈 a 中元素的数量。

   • empty 操作：时间复杂度为 \(O(1)\)，因为只需要检查两个栈是否为空。

2. 空间复杂度：

   • 总共使用了两个栈 a 和 b，在最坏情况下，两个栈中存储的元素总数与队列中元素数量相同，所以空间复杂度为 \(O(n)\)，其中 n 为队列中元素的最大数量。