矩阵中的矩形
统计子矩阵个数
满足单调性,用双指针优化。
最大矩形
满足单调性,且满足可合并性。故可进一步用单调栈优化,但当它求个数时,亦要$O(n^3)$
区间DP
扰乱字符串
一道很有意义的区间DP,一般而言,一维区间dp是在一个数组上做的,时间复杂度一般为$O(n^3)$(常见),也可以为$O(n^2)$,而这个二维dp是在两个数组上做的,时间复杂度为$O(n^4)$。
半满足性题目
寻找旋转排序数组中的最小值 II
链内单调递增,链外单调递减。这里最多只有两条链,但理论上并不限制链条数,其中。这里是求最小值,也可以求最大值。
贪心
最多能完成排序的块 II
题解
寻找区间边界性质,寻找各区间最值性质,区间计数,区间和性质。
可切分性质:
思想一:设区间为[a,b],原数组与排好序的数组满足在[a,b]中,所有不同的数字个数相同,转化为差值全为零。
思想二:设区间为[a,b],如果b处可切分,则满足[0,b]的最大值<=[b+1,n-1]的最小值。[t,n-1]的右边界设为一个很大的值即可。
思想三:每个区间的最大值压入栈中,其值是单调的。初始时将每个元素分开,若破坏了单调性则进行合并,最后看栈的大小即知区间大小。
多路归并题-找出数组的第 K 大和
很经典的一道题