P4814 合理的栈顺序（基础）

解题思路

1. 理解题意。 第一行字符串是字符们进栈的顺序，第二行是我们期望的出栈顺序。要检查这个出栈顺序能不能真的实现，就用一个栈把过程模拟一遍。
2. 依次处理每个目标字符。 设目标字符串是 target。从左到右看每个需要弹出的字符 need：只要当前栈为空，或者栈顶不是 need，就从进栈字符串里取出下一个还没进栈的字符，压入栈中。
3. 判断失败。 如果进栈字符串里的字符已经全部用完了，栈顶仍然不是 need，说明不可能弹出 need，这个出栈顺序不合理，输出 "error" 并结束。
4. 弹出成功。 当栈顶正好是 need 时，把它弹出（top 减一），继续处理下一个目标字符。
5. 可能重复。 字符串里可能出现重复字符（比如 aabc 里有两个 a），但这个方法依然正确：因为我们严格按进栈顺序去压、严格按目标顺序去弹，只要模拟能走通就合理。全部目标字符都能弹出，就输出 "right"。

参考代码

// 合理的栈顺序：第一行是各字符的进栈顺序，第二行是出栈顺序，用栈模拟判断出栈顺序是否合理
#include <iostream>
using namespace std;

int main() {
    char input[300];    // 进栈顺序字符串
    char target[300];   // 期望的出栈顺序字符串
    cin >> input;
    cin >> target;
    char stack[300];    // 模拟字符栈
    int top = 0;        // 栈顶（栈内元素个数）
    int idx = 0;        // 下一个还没进栈的字符在input中的下标
    int len = 0;
    while (target[len] != '\0') len++;
    for (int i = 0; i < len; i++) {
        char need = target[i];
        // 不断把后面的字符压入栈，直到栈顶就是要弹出的字符
        while (top == 0 || stack[top - 1] != need) {
            if (input[idx] == '\0') {   // 进栈序列已经全部用完仍无法匹配
                cout << "error" << endl;
                return 0;
            }
            stack[top++] = input[idx++];
        }
        top--;   // 弹出栈顶字符
    }
    cout << "right" << endl;
    return 0;
}

复杂度分析

进栈字符串里的每个字符最多被压入栈一次、弹出一次，目标字符串的每个字符也只看一次，所以时间复杂度是 O(len1+len2)，其中 len1、len2 都是字符串长度（不超过 255）。空间上只用了一个长度 300 的数组当栈，是 O(len1)。