思路：贪心模拟

贪心的根据当前元素与队列两端元素的大小关系，选择小的来插入，以确保队列单调不降。如果无法满足条件，则返回 "NO"。

代码

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main{
    public static String canFormNonDecreasingQueue(int n, int[] a) {
        Deque<Integer> q = new ArrayDeque<>();
        for (int num : a) {
            if (q.isEmpty()) { // 如果队列为空，直接放入
                q.add(num);
            } else {
                // 比较并决定放入左端还是右端
                if (num >= q.peekLast()) { // 如果当前元素大于等于右端元素，放右边
                    q.add(num);
                } else if (num <= q.peekFirst()) { // 如果当前元素小于等于左端元素，放左边
                    q.addFirst(num);
                } else { // 如果两者都不符合，返回 NO
                    return "NO";
                }
            }
        }
        return "YES";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 读取测试案例数量
        StringBuilder results = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt(); // 读取每个测试案例的元素数量
            int[] a = new int[n];
            for (int j = 0; j < n; j++) {
                a[j] = scanner.nextInt(); // 读取元素
            }
            results.append(canFormNonDecreasingQueue(n, a)).append("\n");
        }
        System.out.print(results); // 输出所有结果
        scanner.close();
    }
}

python

from collections import deque

def can_form_non_decreasing_queue(n, a):
    q = deque()
    for num in a:
        if not q:  # 如果队列为空，直接放入
            q.append(num)
        else:
            # 比较并决定放入左端还是右端
            if num >= q[-1]:  # 如果当前元素大于等于右端元素，放右边
                q.append(num)
            elif num <= q[0]:  # 如果当前元素小于等于左端元素，放左边
                q.appendleft(num)
            else:  # 如果两者都不符合，返回 NO
                return "NO"
    return "YES"

def main():
    T = int(input())  # 读取测试案例数量
    results = []
    
    for _ in range(T):
        n = int(input())  # 读取每个测试案例的元素数量
        a = list(map(int, input().split()))  # 读取元素
        results.append(can_form_non_decreasing_queue(n, a))
    
    print("\n".join(results))  # 输出所有结果

if __name__ == "__main__":
    main()

cpp

#include <iostream>
#include <deque>
#include <vector>
#include <string>

using namespace std;

string canFormNonDecreasingQueue(int n, vector<int>& a) {
    deque<int> q;
    for (int num : a) {
        if (q.empty()) { // 如果队列为空，直接放入
            q.push_back(num);
        } else {
            // 比较并决定放入左端还是右端
            if (num >= q.back()) { // 如果当前元素大于等于右端元素，放右边
                q.push_back(num);
            } else if (num <= q.front()) { // 如果当前元素小于等于左端元素，放左边
                q.push_front(num);
            } else { // 如果两者都不符合，返回 NO
                return "NO";
            }
        }
    }
    return "YES";
}

int main() {
    int T;
    cin >> T; // 读取测试案例数量
    string results;

    for (int i = 0; i < T; i++) {
        int n;
        cin >> n; // 读取每个测试案例的元素数量
        vector<int> a(n);
        for (int j = 0; j < n; j++) {
            cin >> a[j]; // 读取元素
        }
        results += canFormNonDecreasingQueue(n, a) + "\n"; // 将结果加入结果字符串
    }
    cout << results; // 输出所有结果
    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小苯有一个长度为$n$的数组$a_1,a_2,...,a_n$，和一个初始为空的双端队列$q$。在这里，双端队列是一种数据结构，其两端都可以放入元素，你可以参考样例解释获得更形象的说明。

他想要将数组中的元素从左到右依次取出、放入$q$中。是否存在一种放入方式，使得全部数字放入后，$q$中的元素从左到右单调不降。

单调不降是指对于$q$中从左到右的第$i$个元素$q$，如果$q_{i+1}$存在，那么$q_i≤q_{i+1}$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^4$)代表数据组数，每组 测试数据描述如下: 第一行输入一个正整数$n$($1≤n≤2×10^5$)代表数组中的元素数量。

第二行输入$n$个整数$a_1，a_2...,a_n$($1≤a_i≤10^9$)代表数组中的元素。

除此之外，保证所有的$n$之和不超过$2×10^5$。

输出描述

对于每一组测试数据，如果存在这样的放入方式，在一行上输出$YES$，否则，直接输出$NO$。

样例1

输入

3
4
2 3 1 4
3
1 1 1
3 
1 3 2

输出

YES
YES
NO

说明

对于第一组测试数据，$[]→[2] → [2, 3] → [1,2, 3]→[1, 2,3,4]$。 对于第二组测试数据，$[]→ [1] → [1,1]→[1,1,1]$。 注意，上述列出的只是其中一种合法的放入方式，并不代表唯一解。