Java版本,第四个会超时, 求优化,谢谢
查看原帖
Java版本,第四个会超时, 求优化,谢谢
993680
congege楼主2023/5/21 12:16
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * @Author congge
 * @Date 2023/5/20 19:26
 * @description https://www.luogu.com.cn/problem/P4387
 * 【深基15.习9】验证栈序列
 */
public class Main {
    public static void main(String[] args) {
        Input sc = new Input();

        int q = sc.nextInt();
        StringBuilder ans = new StringBuilder();


        while (q-- > 0) {


            int n = sc.nextInt();

            // 该元素在栈中的位置
            HashMap<Integer, Integer> map = new HashMap<>();
            
            // 该元素是否已经出栈
            boolean[] polled = new boolean[n];

            for (int i = 0; i < n; i++) {
                map.put(sc.nextInt(), i);
            }
            
            // 存储栈顶元素大小
            LinkedList<Integer> maxList = new LinkedList<>();

            maxList.add(-1);


            // 是否有错版
            boolean flg = false;

            for (int i = 0; i < n; i++) {
                int pollElement = sc.nextInt();
                int pollIndex = map.get(pollElement);

                polled[pollIndex] = true;

                int size = maxList.size();
                if (pollIndex < maxList.get(size - 1)) {
                    flg = true;
                } else if (pollIndex == maxList.get(size - 1)) {
                    while (--pollIndex > 0) {
                        if (!polled[pollIndex]) {
                            break;
                        }
                    }
                    maxList.set(size - 1, pollIndex);
                } else {
                    while (--pollIndex > 0) {
                        if (!polled[pollIndex]) {
                            break;
                        }
                    }
                    maxList.add(pollIndex);
                }
            }
            if (flg) {
                ans.append("No");
            } else {
                ans.append("Yes");
            }
            ans.append('\n');
        }

        System.out.print(ans);
    }

    static class Input {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }
    }
}
2023/5/21 12:16
加载中...