单调栈

Posted on | In ,

经典问题

题意

给一个长度为n的数列 $a[1],a[2],…,a[n]$.对于每个i,求出最小的j,满足a[j]-a[i]>=D

分析

当D=0时，这是常见的单调栈问题，维护一个单调递减的栈，每次更新就是当前数 > 栈顶元素，O(n)便可以解决

当D≠0时， 单调栈上二分

HDU3530

题意

给定一段序列，求出最长的一段子序列使得该子序列中最大最小只差x满足m<=x<=k。

分析