题目内容

小塔喜欢解决各种数学难题。一天，他遇到了一道有趣的题目：他需要帮助他的朋友们完成一个排序任务。小塔得到两个长度为$n$的数组$a[]$和$b[]$。他可以在两个数组对应位置进行交换，即选定一个位置$i$，交换$a[i]$和$b[i]$。他可以进行任意交换(包括$0$次)，他想知道按最优策略来是否可以达成让至少一个数组，$a[]$或者$b[]$，变得有序。有序即数组单调不减(升序)或者单调不增(降序)均可。形式化地，给定两个长度为$n$的数组$a[]$和$b[]$。你可以任选一个位置$i$交换$a[i]$和$b[i]$，可以进行任意多次这样的操作。你的目标是判断是否能够通过这些操作使得至少一个数组变得有序(升序或降序)。小塔想要在老师面前证明自己，但这个题目实在有点太难了，请你帮帮他!

输入描述

单调栈

题目要求单调递增，或单调递减的数组一个位置可以用两个数$\\$ 假设使用的数都放进c数组 1.对于单调递减肯定是前面越大越好，对于每个i如果a[i]和b[i]之中的最大的都<c[i-1]，那么选最大的否则选小的，保证每一步都是最有，如果最小的都大于c[i-1]那么无法构造成功. 单调递增同理，也可以选择反转a,b数组进行做单调递减.$\\$ 整体时间复杂度o(n)