二重式
分治法
中位数
运用彩虹排序的思想,把数组分为三个区域,分别为大于,等于,小于pivot的.
|
|
单调栈
单调栈,顾名思义就是说栈内的元素,按照某种方式排序下,必须是单调的。如果新入栈的元素破坏了单调性,就弹出栈内元素,直到满足单调性。
单调栈: 到底什么时候该用?
答: 在一个线性数据结构中,
为任意一个元素找左边和右边第一个比自己大/小的位置,用单调栈
为任意一个元素找左边最大的和右边最大的位置,用two pointers
单调栈是一个维护型的数据结构,我觉得面试的时候你跟面试官说你打算怎么维护他即可,说出了“单调栈“这个词反而显得你做过这道题。这个概念有点像DP,你忽然说了一个“背包型动态规划”反而会引起别人的警觉,觉得你是老司机刷过这道题
右边第一个大数
对于一个数组中的所有元素, 求出右边第一个比该元素大的数的位置. 如果右边不存在比该元素大的数,返回-1;
例:
[3,1,5,2,4,6]
[2,2,5,4,5,-1]
维护一个单调非增的栈, 如果栈为空或者小于等于栈顶元素,就可以入栈,否则就把之前比该元素都小的元素都出栈,并且计算相应的返回值.
|
|
Largest Rectangle in Histogram[https://leetcode.com/problems/largest-rectangle-in-histogram/description]
|
|
最大区间权值
区间权值定义为 区间内最小的数*区间和
比如 [3,1,6] 一共有6个子区间, 权值分别是:
[3] 9
[1] 1
[6] 36
[3,1] 4
[1,6] 6
[3,1,6] 10
思路:
- 如果数组元素非负, 那么可以直接求以每个元素为最小值的最大区间. 维护一个单调非增的栈
- 如果元素任意,找到区间之后再逐个求.
现假定是第一种情况
|
|
构造MaxTree
给定一个没有重复元素的数组A,定义A上的MaxTree如下:MaxTree的根节点为A中最大的数,根节点的左子树为数组中最大数左边部分的MaxTree,右子树为数组中最大数右边部分的MaxTree。请根据给定的数组A,设计一个算法构造这个数组的MaxTree。
答:
如果能够确定每个节点的父亲节点,则可以构造出整棵树。找出每个数往左数第一个比他大的数和往右数第一个比他大的数,两者中较小的数即为该数的父亲节点。如:[3,1,2],3没有父亲节点,1的父亲节点为2,2的父亲节为3。并且可以根据与父亲的位置关系来确定是左儿子还是右儿子。接下来的问题是如何快速找出每个数往左、往右第一个比他大的数。这里需要用到数据结构栈。以找每个数左边第一个比他大的数为例,从左到右遍历每个数,栈中保持递减序列,新来的数不停的Pop出栈顶直到栈顶比新数大或没有数。以[3,1,2]为例,首先3入栈,接下来1比3小,无需pop出3,1入栈,并且确定了1往左第一个比他大的数为3。接下来2比1大,1出栈,2比3小,2入栈。并且确定了2往左第一个比他大的数为3。用同样的方法可以求得每个数往右第一个比他大的数。时间复杂度O(n),空间复杂度也是O(n)为最优解法。