栈和队列
1.栈
232. 用栈实现队列
题目难度：简单 用时： 5 分钟 标记： 完成
class MyQueue {
public:
stack<int> ins;
stack<int> outs;
MyQueue() {
}
void push(int x) {
ins.push(x);
}
int pop() {
while (!ins.empty())
{
outs.push(ins.top());
ins.pop();
}
int temp = outs.top();
outs.pop();
while (!outs.empty())
{
ins.push(outs.top());
outs.pop();
}
return temp;
}
int peek() {
while (!ins.empty())
{
outs.push(ins.top());
ins.pop();
}
int temp = outs.top();
while (!outs.empty())
{
ins.push(outs.top());
outs.pop();
}
return temp;
}
bool empty() {
return ins.empty();
}
};
225. 用队列实现栈
题目难度：简单 用时： 5 分钟 标记： 完成
class MyStack {
public:
queue<int> quess;
queue<int> be;
MyStack() {
}
void push(int x) {
quess.push(x);
}
int pop() {
be = quess;
int i = 0;
while (!quess.empty())
{
quess.pop();
}
while (i<be.size()-1)
{
quess.push(be.front());
be.pop();
}
return be.front();
}
int top() {
return quess.back();
}
bool empty() {
return quess.empty();
}
};
20. 有效的括号
题目难度：简单 用时： 9 分钟 标记： 完成
class Solution {
//栈
public:
bool isValid(string s) {
if (s.size() % 2 == 1) return false; //奇数直接返回
stack<char> stack_str;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') stack_str.push(s[i]);
else
{
if (stack_str.empty()) return false;
char ch = stack_str.top();
stack_str.pop();
if (s[i] == ')' && ch == '(') continue;
else if (s[i] == ']' && ch == '[') continue;
else if (s[i] == '}' && ch == '{') continue;
else return false;
}
}
if (stack_str.empty()) return true;
else return false;
}
};
1047. 删除字符串中的所有相邻重复项
题目难度：简单 用时： 10 分钟 标记： 完成
class Solution {
public:
string removeDuplicates(string s) {
stack<char> stacks;
for (int i = 0; i < s.size(); ++i) {
if (!stacks.empty() && stacks.top()==s[i])stacks.pop();
else stacks.push(s[i]);
}
string res;
while (!stacks.empty())
{
res.push_back(stacks.top());
stacks.pop();
}
std::reverse(res.begin(), res.end());
return res;
}
};
150. 逆波兰表达式求值
题目难度：中等 用时： 10 分钟 标记： 完成
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> sta;
for (int i = 0; i < tokens.size(); ++i) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" ||tokens[i] == "/" )
{
int b = sta.top();
sta.pop();
int a = sta.top();
sta.pop();
if (tokens[i] == "+") sta.push(a+b);
if (tokens[i] == "-") sta.push(a-b);
if (tokens[i] == "*") sta.push(a*b);
if (tokens[i] == "/") sta.push(a/b);
} else
{
sta.push(stoi(tokens[i]));
}
}
return sta.top();
}
};
2.队列
239. 滑动窗口最大值（单调队列）
题目难度：困难 用时： 25 分钟 标记： 未完成
class Solution {
public:
class MyQueue { //单调队列（从大到小）
public:
deque<int> que; // 使用deque来实现单调队列
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 同时pop之前判断队列当前是否为空。
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return que.front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result;
for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
que.push(nums[i]);
}
result.push_back(que.front()); // result 记录前k的元素的最大值
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i - k]); // 滑动窗口移除最前面元素
que.push(nums[i]); // 滑动窗口前加入最后面的元素
result.push_back(que.front()); // 记录对应的最大值
}
return result;
}
};
347. 前 K 个高频元素（优先级队列）
题目难度：中等 用时： 10 分钟 标记： 未完成
要统计元素出现频率
对频率排序
找出前K个高频元素
首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。
其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。
priority_queue <node, vector<node>, cmp>优先级队列创建方式：node为存储结构，第二个参数是vector定义的存储结构，cmp是比较函数
//347. 前 K 个高频元素
class Solution {
class compare
{
public:
bool operator()(const pair<int,int> &a ,const pair<int,int> &b)
{
return a.second > b.second;
}
};
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> maps;
for (int i = 0; i < nums.size(); ++i) {
maps[nums[i]]++;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> que;
for (auto it:maps) {
que.push(it);
if (que.size() > k) que.pop();
}
vector<int> res;
res.resize(k);
for (int i = res.size() -1; i>=0; --i) {
res[i] =que.top().first;
que.pop();
}
return res;
}
};
23. 合并 K 个升序链表（优先级队列）
class Solution {
struct Comp {
bool operator() (ListNode* l1, ListNode* l2) {
return l1->val > l2->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0 ) return NULL;
priority_queue<ListNode*, vector<ListNode*>, Comp> que;
for (auto x:lists) {
if (x) que.push(x);
}
ListNode* res = new ListNode(-1);
ListNode* pre = res;
while (!que.empty())
{
ListNode* temp = que.top();
res->next = temp;
que.pop();
res = res->next;
temp = temp->next;
if (temp) que.push(temp);
}
res->next = NULL;
return pre->next;
}
};
3.单调栈
739. 每日温度
题目难度： 中等 用时： 15 分钟 标记： 完成
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> stacks;
vector<int> res(temperatures.size());
for (int i = 0; i < temperatures.size(); ++i) {
while (!stacks.empty() && temperatures[stacks.top()] < temperatures[i])
{
res[stacks.top()] = i - stacks.top();
stacks.pop();
}
stacks.push(i);
}
return res;
}
};
496. 下一个更大元素 I
题目难度： 中等 用时： 15分钟 标记： 完成
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int>res(nums1.size(),-1);
stack<int> stacks;
unordered_map<int,int> umap;
for (int i = 0; i < nums1.size(); ++i) {
umap[nums1[i]] = i;
}
for (int i = 0; i < nums2.size(); ++i) {
while (!stacks.empty() && nums2[stacks.top()] < nums2[i])
{
int top = stacks.top();
stacks.pop();
if (umap.find(nums2[top])!=umap.end())
res[umap[nums2[top]]] = nums2[i];
}
stacks.push(i);
}
return res;
}
};
503. 下一个更大元素 II
题目难度： 中等 用时： 10分钟 标记： 完成
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int>res(nums.size(),-1);
stack<int> stacks;
for (int i = 0; i < nums.size() * 2; ++i) {
while (!stacks.empty() && nums[stacks.top()] < nums[i % nums.size()])
{
res[stacks.top()] = nums[i % nums.size()];
stacks.pop();
}
stacks.push(i % nums.size());
}
return res;
}
};
42. 接雨水（未）
题目难度： 困难 用时： 20分钟 标记： 未完成
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int res = 0;
st.push(0);
for (int i = 0; i < height.size(); ++i) {
if (height[st.top()] == height[i]) st.pop();
while (!st.empty() && height[st.top()] < height[i] )
{
int before = st.top();
st.pop();
if (!st.empty())
{
int w = i - st.top() - 1;
int h = min(height[st.top()],height[i]) -height[before] ;
res+=w*h;
}
}
st.push(i);
}
return res;
}
};
84. 柱状图中最大的矩形（未）
题目难度： 困难 用时： 20分钟 标记： 未完成
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = 0;
stack<int> stacks;
//前后加入0
heights.insert(heights.begin(),0);
heights.push_back(0);
stacks.push(0);
for (int i = 1; i < heights.size(); ++i) {
while (!stacks.empty() && heights[stacks.top()] > heights[i])
{
int mid = stacks.top();
stacks.pop();
int right = stacks.top();
int h = heights[mid];
int w = i - right - 1;
res = max(res,h*w);
}
stacks.push(i);
}
return res;
}
};
901. 股票价格跨度
class StockSpanner {
stack<pair<int,int>> st;
int count;
public:
StockSpanner() {
count = 0;
}
int next(int price) {
while(!st.empty() && st.top().first <= price)
{
st.pop();
}
if(!st.empty())
{
pair<int,int> temp = st.top();
st.push({price,count++});
return count - temp.second - 1;
}
else
{
st.push({price,count++});
return count;
}
}
};