9 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 $appendTail$ 和 $deleteHead$ ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，$deleteHead$ 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]提示：
- $1 <= values <= 10000$
- 最多会对$ appendTail、deleteHead $进行$ 10000$ 次调用
题解
class CQueue {
stack<int> inStack, outStack;
void in2out()
{
while(!inStack.empty())
{
outStack.push(inStack.top());
inStack.pop();
}
}
public:
CQueue() {
}
void appendTail(int value) {
inStack.push(value);
}
int deleteHead() {
if(outStack.empty())
{
if(inStack.empty())
{
return -1;
}
in2out();
}
int value =outStack.top();
outStack.pop();
return value;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/30（155） 包含 min 函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.提示：
- 各函数的调用总次数不超过 20000 次
题解
/*
* @lc app=leetcode.cn id=155 lang=cpp
*
* [155] 最小栈
*/
// @lc code=start
class MinStack {
stack<int> m_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(__INT_MAX__);
}
void push(int val) {
m_stack.push(val);
min_stack.push(::min(min_stack.top(),val));//::写法（使用全局变量，避免与局部变量冲突）
}
void pop() {
m_stack.pop();
min_stack.pop();
}
int top() {
return m_stack.top();
}
int getMin() {
return min_stack.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
// @lc code=end
31（946） 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。提示：
- $0 <= pushed.length == popped.length <= 1000$
- $0 <= pushed[i], popped[i] < 1000$
- $pushed$ 是 $popped$ 的排列。
/*031*/
/*946*/
/*
* @lc app=leetcode.cn id=946 lang=cpp
*
* [946] 验证栈序列
*/
// @lc code=start
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> m_stack;
int i=0;
for(int num: pushed)
{
m_stack.push(num);
while(!m_stack.empty() && m_stack.top()==popped[i])
{
m_stack.pop();
i++;
}
}
return m_stack.empty();//不为空即无此出入栈顺序
}
};
// @lc code=end
40 最小的 K 个数
输入整数数组 $arr$ ，找出其中最小的 $k$ 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]限制：
- $0 <= k <= arr.length <= 10000$
- $0 <= arr[i] <= 10000$
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
sort(arr.begin(),arr.end());
vector<int> res;
for(int i=0;i<k;i++)
{
res.push_back(arr[i]);
}
return res;
}
};41（295） 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]限制：
- 最多会对 $addNum、findMedian$ 进行 $50000$ 次调用。
题解
/*295*/
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> queMin;//降序排列，大顶堆less
priority_queue<int, vector<int>, greater<int>> queMax;//升序排列 小顶堆great
MedianFinder() {}
void addNum(int num) {
if(queMin.empty()||num<=queMin.top())//num小于等于中位数
{
queMin.push(num);
if(queMax.size()+1<queMin.size())
{
queMax.push(queMin.top());
queMin.pop();
}
}
else
{
queMax.push(num);
if(queMax.size()>queMin.size())
{
queMin.push(queMax.top());
queMax.pop();
}
}
}
double findMedian() {
if(queMin.size()>queMax.size())
{
return queMin.top();
}
return (queMin.top()+queMax.top())/2.0;
}
};50 字符流中第一个不重复的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = "abaccdeff"
输出：'b'示例 2:
输入：s = ""
输出：' '限制：
0 <= s 的长度 <= 50000题解
class Solution {
public:
char firstUniqChar(string s) {
if(s=="")return ' ';
unordered_map<char, bool> map;
for(int i=0;i<s.size();i++)
{
map[s[i]]=(map.find(s[i])==map.end());
}
for(int i=0;i<s.size();i++)
{
if(map[s[i]])
return s[i];
}
return ' ';
}
};59 - I（239） 滑动窗口的最大值
给定一个数组 $nums$ 和滑动窗口的大小 $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提示：
你可以假设 k 总是有效的，在输入数组 不为空 的情况下，$1 ≤ k ≤ nums.length$。
题解
/*
* @lc app=leetcode.cn id=239 lang=cpp
*
* [239] 滑动窗口最大值
*/
// @lc code=start
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n= nums.size();
if(n==0||k==0)return {};
//滑动窗口左右
int left = -k+1;//左右相差（k-1）
int right = 0;
deque<int> deq;//双端队列
vector<int> res;
while(right<n)
{
//判断上次循环左边是否是最大元素，是就pop掉，滑窗开始移动才需要判断
if(left >= 1 && nums[left-1] == deq[0])
deq.pop_front();
while(!deq.empty() && deq[0] < nums[right])//小于nums[right]元素出队
deq.pop_front();
while(!deq.empty() && deq[deq.size()-1] < nums[right])//小于nums[right]元素出队,队头队尾检查一边保证单调递减，去掉该检查会导致如3,1情况下入2时，1不能及时出掉[1,3,1,2,0,5]
deq.pop_back();
deq.push_back(nums[right]);//right进队列
if(left>=0) res.push_back(deq[0]);//滑窗形成
left++;
right++;
}
return res;
}
};
// @lc code=end
