翔村渡渡鸟
翔村渡渡鸟
未归档
关于最长上升子序列啥时候该用upper_bound or lower_bound
全部文章
未归档
# ACM-kmp(2)
# ACM-二分(3)
# ACM-位运算(5)
# ACM-前缀和(2)
# ACM-双指针(1)
# ACM-差分(2)
# ACM-数论(8)
# ACM-构造题(1)
# ACM-枚举(4)
# ACM-模拟(2)
# ACM-离散化(1)
# ACM-线段树(1)
# ACM-贪心(5)
# ACM-高精度(1)
# dfs(3)
# dp(5)
# 优先队列(1)
# 字符串(4)
# 最短路(2)
# 栈(6)
atcoder(5)
bfs(1)
cf(1)
dfs(1)
map(2)
mooc(1)
pta(2)
qsort(1)
STL(1)
Uva(1)
vector(1)
二分(1)
前缀和(1)
动态规划(4)
字符串(2)
学习方法(1)
思维(5)
排列组合(3)
排序(1)
数学(2)
数据结构(1)
枚举(1)
栈(1)
洛谷(1)
牛客竞赛(6)
知识点(2)
竞赛技巧(1)
算法(2)
算法知识点(1)
精度(1)
紫书(6)
蓝桥杯(16)
贪心(2)
队列(1)
题解(8)
归档
标签
去牛客网
登录
/
注册
关于最长上升子序列啥时候该用upper_bound or lower_bound
505 浏览
0 回复
2021-01-29
翔村渡渡鸟
+关注
维护的是一个严格单增的序列:则需要找到单调栈中第一个大于等于他的数(lower_bound),如果直接找第一个大于他的数找到替换,那么当单调栈中存在一个和他相等的数,则单调栈不再严格单增
维护的是一个非减的序列:则需要找到第一个大于它的数(upper_bound),找到后替换即可,因为这样提供一个更多相等序列的机会,比如单调栈中是1 2 2 3,而当前元素是2 ,那么新的单调栈是1 2 2 2,而不应该是1 2 2 3
举报
收藏
赞
评论加载中...