μ€ν(Stack)
λ¬Έμ
https://www.acmicpc.net/problem/4949
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(void)
{
while (1) {
string s;
getline(cin, s);
if (s.length() == 1 && s[0] == '.')
break;
stack<char> st;
bool flag = true;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[')
st.push(s[i]);
else if (s[i] == ']' || s[i] == '}' || s[i] == ')') {
if (!st.empty() && (st.top() == '[') && (s[i] == ']'))
st.pop();
else if (!st.empty() && (st.top() == '{') && (s[i] == '}'))
st.pop();
else if (!st.empty() && (st.top() == '(') && (s[i] == ')'))
st.pop();
else {
flag = false;
break;
}
}
}
if (flag && st.empty())
cout << "yes\n";
else
cout << "no\n";
}
return 0;
}
https://www.acmicpc.net/problem/1874
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
stack<int> s;
vector<char> v;
int num = 0, tmp;
while (n--) {
cin >> tmp;
while (s.empty() || s.top() < tmp) {
if (num > tmp) {
cout << "NO\n";
return 0;
}
s.push(++num);
v.push_back('+');
}
if (s.top() >= tmp) {
s.pop();
v.push_back('-');
}
}
for (char c : v)
cout << c << "\n";
}
https://www.acmicpc.net/problem/1406
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
string s;
cin >> s;
stack<char> StackL, StackR;
for (int i = 0; i < s.length(); i++)
StackL.push(s[i]);
int M;
cin >> M;
while (M--) {
cin >> s;
if (s == "L") {
if (!StackL.empty()) {
StackR.push(StackL.top());
StackL.pop();
}
}
else if (s == "D") {
if (!StackR.empty()) {
StackL.push(StackR.top());
StackR.pop();
}
}
else if (s == "B") {
if (!StackL.empty())
StackL.pop();
}
else if (s == "P") {
char tmp;
cin >> tmp;
StackL.push(tmp);
}
}
while (!StackL.empty()) {
StackR.push(StackL.top());
StackL.pop();
}
while (!StackR.empty()) {
cout << StackR.top();
StackR.pop();
}
}
https://www.acmicpc.net/problem/6549
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int main()
{
int n;
while (cin >> n && n) {
vector<int> height(n + 1);
for (int i = 0; i < n; i++)
cin >> height[i];
stack<int> st;
long long ans = 0;
for (int i = 0; i <= n; i++) {
while (!st.empty() && height[i] < height[st.top()]) {
int t = st.top();
st.pop();
int width = i - (st.empty() ? 0 : st.top() + 1);
ans = max(ans, (long long)height[t] * width);
}
st.push(i);
}
cout << ans << "\n";
}
}
https://leetcode.com/problems/maximal-rectangle/description/
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution
{
public:
int maximalRectangle(vector<vector<char>> &matrix)
{
if (matrix.empty())
return 0;
int answer = 0;
int c = matrix[0].size();
vector<int> h(c + 1, 0);
for (auto &v : matrix)
{
for (int i = 0; i < c; ++i)
h[i] = v[i] == '0' ? 0 : h[i] + 1;
stack<int> s;
for (int i = 0; i <= c;)
{
if (s.empty() || h[i] >= h[s.top()])
s.push(i++);
else
{
int cur = s.top();
s.pop();
answer = max(answer, h[cur] * (s.empty() ? i : (i - s.top() - 1)));
}
}
}
return answer;
}
};
https://leetcode.com/problems/trapping-rain-water/
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution
{
public:
int trap(vector<int> &height)
{
int answer = 0;
stack<int> s;
for (int i = 0; i < height.size(); ++i)
{
while (!s.empty() && height[i] > height[s.top()])
{
int top = s.top();
s.pop();
if (s.empty())
break;
int value = min(height[i], height[s.top()]) - height[top];
int distance = i - s.top() - 1;
answer += value * distance;
}
s.push(i);
}
return answer;
}
};
https://leetcode.com/problems/min-stack/description/
#include <stack>
using namespace std;
class MinStack {
public:
stack<int> s;
stack<int> minS;
MinStack() {
}
void push(int val) {
minS.push((s.empty() || minS.top() > val) ? val : minS.top());
s.push(val);
}
void pop() {
s.pop();
minS.pop();
}
int top() {
return s.top();
}
int getMin() {
return minS.top();
}
};