标签：复杂度 链表 Minimum 答案 Permutation 考虑 ABC299G 单调
ABC229G洛谷链接
atcoder链接
- 容易发现如果最终答案有两个相邻的数 \(b_i,b_{i+1}\) 满足 \(b_i>b_{i+1}\) 且 \(b_i\) 之后出现过，则显然可以找到另一个不劣的答案不满足这个性质
- 先说一个错误的结论：从前往后考虑，用链表维护答案，对于加入的一个数 \(a_i\) ，如果之前在 \(a_j\) 出现过，并且答案中这个的下一个数 \(< a_j\) 则在链表中删除这个位置，并在插入在链表末尾
- 这个思路是错误的，Hack:
2 3 1 2 3 ，因为 \(2\) 认为自己比 \(3\) 小，因此并不会替换到链表的末尾。
- 上面思路错误的原因是没有考虑到自这个数之后对答案的影响。但如果我们暴力考虑后面每一个数复杂度就变成了 \(O(n^2)\)
- 既然让前面的往后考虑不行，那我们试着让后面的向前考虑。考虑单调栈(这里并不是狭义上求左右第一个最大值位置的单调栈，而是参照了单调栈的思路)，对于加入的数 \(a_i\) ，如果这个数没在栈中出现过，则把栈顶所有不满足上述条件的弹出，并把 \(a_i\) 加入栈中，直到考虑完前 \(n\) 个，此时栈中显然有 \(m\) 个元素，便利输出答案即可
- 最终复杂度 \(O(n)\)
标签：复杂度,
链表,
Minimum,
答案,
Permutation,
考虑,
ABC299G,
单调
From： https://www.cnblogs.com/fox-konata/p/17793021.html