3302 ??STL

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eva l() {
    auto b = num.top();
    num.pop();
    auto a = num.top();
    num.pop();
    auto c = op.top();
    op.pop();
    int x;
    if (c == '+')
        x = a + b;
    else if (c == '-')
        x = a - b;
    else if (c == '*')
        x = a * b;
    else
        x = a / b;
    num.push(x);
}

int main() {
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        auto c = str[i];
        if (isdigit(c)) {
            // 第一类双指针
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j++] - '0';
            i = j - 1;  // 考虑i++
            num.push(x);
        } else if (c == '(')
            op.push(c);
        else if (c == ')') {
            while (op.top() != '(') eva l();
            op.pop();
        } else {
            while (op.size() && pr[op.top()] >= pr[c]) eva l();
            op.push(c);
        }
    }
    while (op.size()) eva l();
    cout << num.top() << endl;

    return 0;
}

队列

829

829. 模拟队列 - AcWing题库 队尾插入，队头输出

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int que[N], st = -1, ed = -1;

int main() {
    int m;
    cin >> m;
    while (m--) {
        string str;
        int x;
        cin >> str;
        if (str == "push") {
            cin >> x;
            que[++ed] = x;
        } else if (str == "pop") {
            st++;
        } else if (str == "empty") {
            if (st == ed)
                puts("YES");
            else
                puts("NO");
        } else if (str == "query") {
            cout << que[st + 1] << endl;
        }
    }

    return 0;
}

单调栈

830 ??

830. 单调栈 - AcWing题库

朴素做法是两层循环。

使用栈，满足情况：当下标为 i，栈内元素为 \(a_1,a_2...a_i\)

单调栈要求遍历数组过程中，维护栈，满足栈底至栈顶元素呈单调性（依次递增）

• 栈内 \(a_1\)~\(a_i\) 递增，此时遍历至 \(a_{i+1}\)，将小于 \(a_{i+1}\) 的栈内元素删除，再插入 \(a_{i+1}\)
• 每个元素一次，出栈一次，\(O(n)\)

scanf 与 cin 速度差了十倍左右，使用 cin.tie(0) 或 ios::sync_with_stdio(false) 加速

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int stk[N], tt;

int main() {
    cin.tie(0);
    // ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) tt--;
        if (tt)
            cout << stk[tt] << " ";
        else
            cout << -1 << " ";
        stk[++tt] = x;
    }

    return 0;
}

单调队列

154 ??

154. 滑动窗口 - AcWing题库

朴素算法是 \(O(n^2)\)

单调队列要求滑动窗口每滑动一次时，将窗口内 >= \(a_i\) 的元素从队尾删除（类似单调栈），\(a_i\) 入队，该队列将保持单调递增，此时对头点为最小值。注意队列里存的是下标