动态规划 单调队列优化
时间: 2023-11-07 09:05:02 浏览: 117
动态规划之队列优化1
引用: 单调栈和单调队列是一种常用的优化思想,可以通过维护一个有序的数据结构,排除不可能的决策,提高算法的效率。其中,单调栈适用于解决求解左边第一个比自己大(小)的点等问题,而单调队列适用于维护左区间最值等问题。通过这两种思想,可以优化动态规划等算法的时间复杂度。
引用: 在求解最大子序和问题时,可以使用单调队列优化。假设当前位置为i,我们可以维护一个单调递减的队列,其中存放的是前i个位置的子序和。每次加入新的元素时,可以通过比较队列中的元素和当前元素的大小,若当前元素更大,则弹出队列中的元素,直到队列为空或者队尾元素大于当前元素。然后将当前元素加入队列。最终,队列中的最大值即为最大子序和。
引用: 单调队列优化动态规划是通过将可转移状态存入一个单调队列中,来进行状态转移的一种方法。这个可转移状态要满足连续且单调的特性。具体原理是,如果一个选手比你小,但是比你强,那么你就可以退役了。在动态规划中,可以先使用朴素的dp方法找到一种方法,再根据单调队列优化。
例题1:求左边第1个比自己大的点
问题分析:将可转移给第i个点的对象存入栈中。假设i可以从j,k转移而来,其中j < k。栈中的元素是一个单调递减的栈。每次加入第i个点,都会依次将比ai小的弹出,最后栈顶元素即为答案。
例题2:维护左区间最值
问题分析:通过维护一个单调递减的队列,存储左区间的最值。在每次更新元素时,比较队列中的元素和当前元素的大小,若当前元素更大,则弹出队列中的元素,直到队列为空或者队尾元素大于当前元素。然后将当前元素加入队列。
阅读全文