终于想明白为什么单调队列因入队而删掉的元素不影响最值。
imported
notes
入队的元素出对原因只有2种–过期或者被更大(小)的元素删除 此元素过期那么被删掉的元素均过期,所以不影响。 被删除那么新进入的更大(小)的元素比删掉的元素(更早删除的)仍然更优,所以不影响。 否则此元素仍为最大(小),所以不影响。
September 9, 2011
入队的元素出对原因只有2种–过期或者被更大(小)的元素删除 此元素过期那么被删掉的元素均过期,所以不影响。 被删除那么新进入的更大(小)的元素比删掉的元素(更早删除的)仍然更优,所以不影响。 否则此元素仍为最大(小),所以不影响。