题解

题面描述

有一个栈中有 $n$ 个元素，这 $n$ 个元素就是 $1$ 到 $n$。现在共有 $2n$ 条指令，有两种指令：

• 指令一: push val，往栈压入元素 $val$；
• 指令二: pop，弹出栈顶元素。

你想依次从栈中 pop 出 $1$ 到 $n$，你可以在每一次 push 操作执行完毕后，对栈里的元素进行重新排序（从栈顶到栈底，按从小到大的顺序）。

为了顺利 pop 出 $1$ 到 $n$，最少需要进行多少次重新排序？

思路

我们需要模拟栈的操作并尽可能减少排序次数。具体的思路如下：

1. 栈的模拟：使用栈存储压入的元素，栈的元素会按照 push 和 pop 的顺序进行变化。
2. 弹出顺序的控制：我们需要按照从 $1$ 到 $n$ 的顺序依次弹出栈顶的元素。如果栈顶元素不是当前期望弹出的元素，那么就需要对栈进行排序。
3. 排序操作：每当 pop 的时候，若栈顶元素不符合要求，就进行排序，确保栈顶元素是当前应该弹出的最小元素。
4. 最少排序次数：每当进行一次排序时，我们增加排序次数的计数。

通过模拟栈的操作，保持每次期望弹出最小元素，我们可以记录最少的排序次数。

C++

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>  // 添加这一行

using namespace std;

int main() {
    int n;
    cin >> n;  // 输入栈元素数量
    
    stack<int> st;  // 使用栈来模拟操作
    int next_pop = 1;  // 当前期望弹出的元素
    int sort_count = 0;  // 记录排序的次数
    
    for (int i = 0; i < 2 * n; ++i) {
        string op;
        cin >> op;
        
        if (op == "push") {
            int val;
            cin >> val;
            st.push(val);  // 执行压栈操作
        } else if (op == "pop") {
            if (st.top() == next_pop) {  // 栈顶元素是期望的元素
                st.pop();  // 弹出栈顶元素
                next_pop++;  // 更新期望的下一个元素
            } else {
                sort_count++;  // 需要进行排序
                vector<int> temp;
                
                // 将栈中的元素弹出并放入临时容器
                while (!st.empty()) {
                    temp.push_back(st.top());
                    st.pop();
                }
                
                // 对临时容器排序
                sort(temp.begin(), temp.end());  // 这里就可以使用sort了
                
                // 将排序后的元素重新压入栈
                for (int i = temp.size() - 1; i >= 0; --i) {
                    st.push(temp[i]);
                }
                
                // 弹出期望的元素
                st.pop();
                next_pop++;  // 更新期望的下一个元素
            }
        }
    }
    
    cout << sort_count << endl;  // 输出最少排序次数
    return 0;
}

Python

def main():
    n = int(input())  # 输入元素数量
    st = []  # 使用列表模拟栈
    next_pop = 1  # 记录下一个应该 pop 的元素
    sort_count = 0  # 记录排序次数
    
    for _ in range(2 * n):
        op = input().split()  # 读取指令
        if op[0] == 'push':
            val = int(op[1])  # 获取压入栈的值
            st.append(val)  # 将 val 压入栈
        elif op[0] == 'pop':
            if st[-1] == next_pop:  # 如果栈顶元素是我们期望的元素
                st.pop()  # 弹出栈顶元素
                next_pop += 1  # 更新期望的下一个元素
            else:
                sort_count += 1  # 需要排序
                # 对栈进行排序
                st.sort(reverse=True)  # 从栈顶到栈底排序
                # 弹出栈顶元素
                st.pop()
                next_pop += 1  # 更新期望的下一个元素

    print(sort_count)

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 输入栈元素数量
        sc.nextLine();  // 消耗掉换行符
        
        Stack<Integer> st = new Stack<>();
        int nextPop = 1;  // 当前期望弹出的元素
        int sortCount = 0;  // 记录排序次数
        
        for (int i = 0; i < 2 * n; ++i) {
            String op = sc.nextLine();  // 读取指令
            if (op.startsWith("push")) {
                int val = Integer.parseInt(op.split(" ")[1]);
                st.push(val);  // 执行压栈操作
            } else if (op.equals("pop")) {
                if (st.peek() == nextPop) {  // 栈顶元素是期望的元素
                    st.pop();  // 弹出栈顶元素
                    nextPop++;  // 更新期望的下一个元素
                } else {
                    sortCount++;  // 需要进行排序
                    // 使用 List 临时存储栈中的元素
                    List<Integer> temp = new ArrayList<>();
                    while (!st.isEmpty()) {
                        temp.add(st.pop());
                    }
                    // 对临时容器排序
                    Collections.sort(temp);
                    // 将排序后的元素重新压入栈
                    for (int i = temp.size() - 1; i >= 0; --i) {
                        st.push(temp.get(i));
                    }
                    // 弹出期望的元素
                    st.pop();
                    nextPop++;  // 更新期望的下一个元素
                }
            }
        }
        
        System.out.println(sortCount);  // 输出最少排序次数
    }
}

题目内容

有一个栈中有$n$个元素，这$n$个元素就是$1$到$n$。现在共有$2*n$条指令，有两种指令:

• 指令一: $push\ val$，往栈压入元素 $val$ ;
• 指令二: $pop$，弹出栈顶元素;

你想依次从栈中 $pop$出$1$~$n$，你可以在每一次指令一执行完毕后，对栈里的元素进行重新排序(从栈顶到栈底、从小到大排序)。

为了顺利 $pop$出$1$~$n$，最少需要进行多少次重新排序。

保证执行 $pop$操作的时候，栈非空，且一定存在一组可行解

输入描述

第一行输入一个整数$n(1≤n≤10^5)$代表元素数量。

此后$2×n$行，每行先输入一个字符串$s$:

如果$s= push$，在同一行上输入一个整数$val (1≤val ≤n)$代表一次指令一;

如果$s= pop$，代表一次指令二。

输出描述

在一行上输出一个整数，代表最少需要进行的重新排序次数。

样例1

输入

3
push 1
pop
push 2
push 3
pop
pop

输出

1

说明

我们要按照顺序拿到$1$~$n$。$push\ 1$，此时栈顶为$1$。$pop$，我们可以拿到$1$，符合要求。$push\ 2$和$push\ 3$，栈里面的元素为$2，3。3$在栈顶。$pop$，如果直接$pop$会拿到$3$，此时我们应该要拿$2$，所以要进行一次排序操作。排序后元素变成3，2。2在栈顶。此时可以拿到2。$pop$，此时可以拿到$3$。进行1次排序就按照顺序拿到了$1$~$n$。

样例2

输入

5
push 1
push 2
push 3
pop
pop
push 4
push 5
pop
POP
PoP

输出

2

说明

$push 1,push 2,push 3$后,栈内元素为{$1,2,3$}，栈顶为$3$。要按照顺序拿到$1$~$n$。下一个操作是$pop$。这时候就需要排序了，排序后变成{$3,2,1$}栈顶为$1$。$pop$，拿到$1$。$pop$拿到2。$push\ 4,push\ 5$栈内元素变成{$3,4,5$}栈顶是$5$，又进行排序，后变成{$5,4,3$}栈顶是$3$。$pop$拿到$3$，$pop$拿到$4$，$pop$拿到$5$。进行$2$次排序就按照顺序拿到了$1$~$n$。