# 411 stack and queue (20. valid parentheses, 1047. delete all adjacent duplicates in the string, 150. inverse Polish expression evaluation, 239. sliding window maximum, 347. the first k high-frequency elements)

2022-06-24 10:02:29

## 20. Valid parenthesis ``````class Solution {

public:
bool isValid(string s) {

stack<int> st;
for (int i = 0; i < s.size(); i++)
{

if (s[i] == '(')
{

st.push(')');
}
else if (s[i] == '{')
{

st.push('}');
}
else if(s[i] == '[')
{

st.push(']');
}
else if (st.empty() || st.top() != s[i])
{

return false;
}
else
{

st.pop();
}
}

return st.empty();
}
};
`````` ## 1047. Delete all adjacent duplicates in the string ``````class Solution {

public:
string removeDuplicates(string s) {

stack<char> st;

for (char s1 : s)
{

if (st.empty() || st.top() != s1)
{

st.push(s1);
}
else
{

st.pop();
}
}

string result = "";
while (!st.empty())
{

result += st.top();
st.pop();
}

reverse(result.begin(), result.end());
return result;
}
};
`````` ## 150. Evaluate the inverse Polish expression ``````class Solution {

public:
int evalRPN(vector<string>& tokens) {

stack<int> st;

for (int i = 0; i < tokens.size(); i++)
{

if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
{

int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();

if (tokens[i] == "+")    st.push(num2 + num1);
if (tokens[i] == "-")    st.push(num2 - num1);
if (tokens[i] == "*")    st.push(num2 * num1);
if (tokens[i] == "/")    st.push(num2 / num1);

}
else
{

st.push(stoi(tokens[i]));
}
}
int res = st.top();
st.pop();
return res;
}
};
`````` ## 239. Maximum sliding window ``````class Solution {

private:
class MyQueue {
// A monotonous queue （ From big to small ）
public:
deque<int> que; //  Use deque To implement monotonic queues
//  Every time it pops up , Compare whether the current value to pop up is equal to the value of the queue exit element , Pop up if equal .
//  meanwhile pop Judge whether the queue is currently empty .
void pop(int value) {

if (!que.empty() && value == que.front()) {

que.pop_front();
}
}
//  If push The value of is greater than the value of the entry element , Then pop up the value at the back of the queue , until push The value of is less than or equal to the value of the queue entry element .
//  This keeps the values in the queue monotonous, from large to small .
void push(int value) {

while (!que.empty() && value > que.back()) {

que.pop_back();
}
que.push_back(value);

}
//  Query the maximum value in the current queue   Directly return to the front of the queue, that is front That's all right. .
int front() {

return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {

MyQueue que;
vector<int> result;
for (int i = 0; i < k; i++) {
//  Before k Put the elements in the queue
que.push(nums[i]);
}
result.push_back(que.front()); // result  Before recording k The maximum value of the element
for (int i = k; i < nums.size(); i++) {

que.pop(nums[i - k]); //  Slide the window to remove the front most element
que.push(nums[i]); //  Add the last element before sliding the window
result.push_back(que.front()); //  Record the corresponding maximum value
}
return result;
}
};
`````` ## 347. front K High frequency elements ``````class Solution {

public:
vector<int> topKFrequent(vector<int>& nums, int k) {

map<int,int> mp;
vector<int> res;

for(int num : nums)
{

mp[num]++;
}

vector<pair<int,int>> vmp;

for(auto it = mp.begin(); it != mp.end(); it++)
{

vmp.push_back({
it->first, it->second});
}

sort(vmp.begin(), vmp.end(),
[](const pair<int, int>& x, const pair<int,int>& y)->int{
return x.second > y.second;});

for(int i = 0; i < k; i++)
{

res.push_back(vmp[i].first);
}

return res;
}
};

`````` 