面试的场景与我们之前学习某个知识点的情况不再相同。在学习“一解多题”的时候，由于已经预设了前提，实际上我们是知道某个题会用到什么知识点的。
但是在面试中，当你拿到一个题目，可能一时想不到具体采用哪种解法。所以在本讲，我将带你回到面试场景，教你分析题目的思路。我们的目标就变成从题目出发，去考虑如何破解一个题。
本讲将会重点学习：
如何挖掘题目的特点
如何利用特点匹配到数据结构和算法知识点
完成这两步动作，需要你熟练地掌握前面“一解多题”模块介绍的数据结构与算法知识点。养兵千日，用在一时，是时候派上用场了。
最大矩形
【题目】给定一个数组，里面有n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：[2,1,5,6,2,3]
输出：10
解释：柱状图的示例，其中每个柱子的宽度为 1，给定的高度为
[2,1,5,6,2,3]
。
输入 最大矩形
暴力算法
当拿到题目之后，一种最简单、最暴力的算法立马会出现在我们脑海里面。那就是：
分别选定两个柱子，然后计算这两个柱子为边界，构成的最大矩形的面积；
取出所有的矩形面积中的最大面积。
那么根据这个思路，可以得到代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
private int minHeight(int[] A, int l, int r) {
int h = Integer.MAX_VALUE;
for (int k = l; k <= r; k++) {
h = Math.min(h, A[k]);
}
return h;
}
public int largestRectangleArea(int[] A) {
final int N = A == null ? 0 : A.length;
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
ans = Math.max(ans,
minHeight(A, i, j) * (j - i + 1));
}
}
return ans;
}
}
|
但是，这个代码的时间复杂度实在太高，达到 O(N3)，在面试中并不能给你加分。那么有没有什么更好的办法呢？
特点 1：区间
可以发现，求解的时候，我们非常依赖一个区域里面的最小值：就是 minHeight() 函数。
那么，有没有什么办法，可以快速地获取：一个数组区间里面的最小值呢？此时问题破解的关键聚焦到下面这个问题上。
给定一个数组：如何快速地查询一个区间里面的最小值？
如果我们能在 O(1) 的时间得到一个区间里面的最小值，那么就可以把暴力算法的时间复杂度优化到 O(N2)。
因此，此时我们需要快速匹配到一个算法和数据结构来满足这样的特点。想到这里，你的脑海里面应该浮现如下的场景：
那么，我们需要什么样的数据结构/算法呢？
如果是在面试中，你发现脑海里面空空如也，一点也想不到有什么办法可以处理这个区间查询问题，就需要立马转换思路，尝试寻找别的破题办法。因为很有可能，这里踩了你的知识盲区，要在短时间发现一种算法解决这个问题的可能性还是挺小的。
如果是在准备面试阶段，那么你应该立马搜索一下有什么样的数据结构可以满足这样的要求。大概率情况下，这种基础问题已经有很多现成的数据结构来支撑了，所以不需要你再去“挠破脑袋”当发明家了。
就现在而言，我们肯定是处在一个准备面试的阶段。所以，下面我会带你走一遍“搜索”的步骤。
求解区间的最小值/最大值问题，一般有 2 类算法与数据结构：
ST（Sparse Table）算法
线段树（Segment Tree）
接下来，我们分别介绍一下这两种算法（说不定哪天你在面试中碰到这个关键问题，就轻而易举答出来了）。
ST 算法
在面试时，我们总是先看到问题，然后希望匹配到一个算法，能够刚好满足我们期望的时间复杂度。那么 ST 算法可以满足我们的要求吗？
先来看一下 ST 算法的特点：
ST 算法需要预处理，并且在预处理阶段，时间复杂度为 O(NlgN)，空间复杂度为 O(NlgN)；
ST 算法预处理结束之后，在查询阶段，时间复杂度为 O(1)。
如果我们用上 ST 算法，那么时间复杂度可以从 O(N3) 变为 O(N2 + NlgN) = O(N2)。这样一来复杂度就下降了一个数量级，还是非常值得一试的。
下面我们讲一下 ST 算法 2 个核心思想。
1. 一分为二
任何一个区间都可以分为两个可能重合的区间。比如给定的区间为 [start, end]，那么：
这个区间可以分为 [start, end1], [start2, end]，即第一个区间必须以 start 为起点，第二个区间必须以 end 为终点；
两个区间可以重合；
两个区间的长度必须是 2p 长度（p 是非负整数）。
【例 1】比如有一个区间 [10, 17]，长度为 8，那么可以拆分为 [10, 13], [14,17] 长度为 22 的两个区间。下图是拆分之后不存在重合的情况：
【例 2】比如有一个区间 [10, 18]，长度为 9。那么可以拆分为 [10, 17] 和 [11, 18] 长度为 23 的两个区间。下图是拆分之后存在部分重合的情况：
【例 3】比如有一个区间 [10, 10]，长度为 1，那么可以拆分为 [10, 10] 和 [10, 10]，这两个区间完全重合，且长度为 20 的两个区间。这是拆分之后完全重合的情况。
基于此，我们可以得到结论 1。
给定一个数组，这个数组里面的任意一个有效区间总是可以表达为：可能重叠的两个 2p 长度区间。
那么，假设我们已经得到所有 2p 长度的区间的信息。那么“区间 [start, end] 上的最小值：可以先取出两个长度为 2p 的子区间的最小值，再从中选择最小的即可。
1
2
|
区间[start, end]上的最小值 = min(区间[l, l+2<sup>p</sup>)上的最小值
区间[r-2<sup>p</sup>+1, r]上的最小值)
|
基于结论 1，我们可以得到结论 2。
计算顺序：
先计算出长度为 20 的所有区间的最小值；
再计算长度为 21 的所有区间的最小值；
然后计算长度为 22 的所有区间的最小值；
直到长度为 2x 的区间的最小值。
其中 2x 刚好大于等于给定的数组长度。
2. 指数表示法
当拆分完成之后，原本一个区间的表示是 [start, end]，分为两个长度（len）一样的区间。更进一步，这两个区间可以表示为 <start1, len>, <start2, len>。
例 1 中 [10, 18] 拆分之后，可以表示为 <start1=10, len=8>, <start2=11, len=8>。
例 2 中 [10, 17] 拆分之后，可以表示为 <start1=10, len=4>, <start2=14,len=4>。
重新表示之后，区间 <start, len> 中，由于长度信息 len 总是 2p，因此我们可以只记录指数 p。
例 1 中 [10, 18] 拆分之后，可以表示为 <start1=10, p=3>, <start2=11, p=3>。
例 2 中 [10, 17] 拆分之后，可以表示为 <start1=10, p=2>, <start2=14,p=2>。
如果我们将区间采用指数 p 表示之后，就只需要使用空间 st[N][log2(N)+1]，也就是空间复杂度为 O(NlgN)。
那么基于以上两个核心思想，我们可以写出 ST 算法的代码了。这里可以分为两步，一步是预处理，另一步是查询。
预处理构建 st[][] 数组代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
void buildST(int[] A, int[][] st) {
final int N = A == null ? 0 : A.length;
// 第一步：
// - 处理长度为1的区间
// 即[i, i + 1)
//
// 区间的表示：
// [start=i, len=2<sup>0</sup>]
// 也就是st[i][len=2<sup>0</sup>]
for (int i = 0; i < N; i++) {
st[i][0] = A[i];
}
// 递推：
// 依次处理2<sup>j</sup>长度。
// 其中2<sup>j</sup> = 2<sup>(j-1)</sup> + 2<sup>(j-1)</sup>
// 注意：这里的长度都是完整的2<sup>j</sup>的
for (int j = 1; (1 << j) <= N; j++) {
// 这里要处理的区间[i, i + (1<<j)]
// last = i + (1<<j)
// 根据左闭右开原则，last是可以取到n的。这点要注意。
for (int i = 0; (i + (1 << j)) <= N; i++) {
st[i][j] = Math.min(st[i][j - 1],
st[i + (1 << (j - 1))][j - 1]);
}
}
}
|
查询阶段的代码如下：
1
2
3
4
5
6
7
8
9
|
int minHeight(int[][] st, int l, int r)
{
// 这里我们将区间[l, r]分为两个区间
// [l, l+log2(len)] => [l, len=log2(len)]
// [r-log2(len)+1, r] => [r-log2(len) + 1, len=log2(len)]
int len = r - l + 1;
int j = log2(len);
return Math.min(st[l][j], st[r - (1 << j) + 1][j]);
}
|
需要注意的是，在查询阶段，如果一个区间的长度本来就是 2p，那么就可以拆分成两个完全重合的区间。
得到 ST 算法的代码之后，我们就可以开始解决这道题目了。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
class Solution {
private int log2(int N) {
return (int)(Math.log(N) / Math.log(2));
}
private int[][] createST(int N) {
final int powerOf2 = log2(N);
int[][] st = new int[N][powerOf2 + 1];
for (int i = 0; i < N; i++) {
st[i] = new int[powerOf2+1];
}
return st;
}
private void buildST(int[] A, int[][] st) {
final int N = A == null ? 0 : A.length;
// 第一步：
// - 处理长度为1的区间
// 即[i, i + 1)
//
// 区间的表示：
// [start=i, len=2<sup>0</sup>]
// 也就是st[i][len=2<sup>0</sup>]
for (int i = 0; i < N; i++) {
st[i][0] = A[i];
}
// 递推：
// 依次处理2<sup>j</sup>长度。
// 其中2<sup>j</sup> = 2<sup>(j-1)</sup> + 2<sup>(j-1)</sup>
// 注意：这里的长度都是完整的2<sup>j</sup>的
for (int j = 1; (1 << j) <= N; j++) {
// 这里要处理的区间[i, i + (1<<j)]
// last = i + (1<<j)
// 根据左闭右开原则，last是可以取到n的。这点要注意。
for (int i = 0; (i + (1 << j)) <= N; i++) {
st[i][j] = Math.min(st[i][j - 1],
st[i + (1 << (j - 1))][j - 1]);
}
}
}
private int minHeight(int[][] st, int l, int r) {
// 这里我们将区间[l, r]分为两个区间
// [l, l+log2(len)] => [l, len=log2(len)]
// [r-log2(len)+1, r] => [r-log2(len) + 1, len=log2(len)]
int len = r - l + 1;
int j = log2(len);
return Math.min(st[l][j], st[r - (1 << j) + 1][j]);
}
public int largestRectangleArea(int[] A) {
final int N = A == null ? 0 : A.length;
int[][] st = createST(N);
buildST(A, st);
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
ans = Math.max(ans,
minHeight(st, i, j) * (j - i + 1));
}
}
return ans;
}
}
|
代码：Java/C++/Python
不过，这种算法的时间复杂度仍然是 O(N2)。这里请你思考一下，还有没有更好的办法呢？
线段树
不妨尝试一下线段树。在处理区间信息的时候，线段树是一个非常有用的数据结构。下面我们来了解一下它的特点（可以先不管它长什么样）：
构建线段树，时间复杂度为 O(NlgN)；
查询阶段，时间复杂度为 O(lgN)；
空间复杂度为 O(4N)。
1. 线段树的思想
线段树的思想是用一棵平衡二叉树来表示一个数组区间上的信息：
根结点记录整个数组的信息；
左子树记录数组左半部分的信息；
右子树记录数组右半部分的信息。
【例 1】 假设给定的数组为 A[] = {1, 2, 3, 4}，需要记录的信息为区间里面的最小值。那么线段树构成如下：
那么查询的时候，就需要从根结点开始往下查。假设我们要基于这棵树查询区间 [1, 3] 的最小值信息。
第 1 步
首先，我们访问到根结点，可以发现 [0, 3] 区间与 [1, 3] 区间处于相交的情况，因此根结点的信息，对于我们要查询的结果是没有帮助的，所以需要将 [0, 3] 区间拆分为 [0, 1] 和 [2,3] 区间。
这里我们得到原则 1：
区间相交的时候，需要拆分树结点区间，然后分别看左右子树。
第 2 步
接下来，我们先看左子树，可以发现区间 [0, 1] 与区间 [1,3] 仍然是处于相交的状态。
因此还需要再次利用原则 1，分别观察它们的左右子树，如下图所示：
我们再接着遍历左右子树的时候，不难发现有以下两种情况:
Case 1. [0,0] 与区间 [1,3] 不相交，无视 [0,0] 区间上的信息；
Case 2. [1,1] 被区间 [1,3] 包含，需要保留这个区间上的信息。
由此，我们就得到原则 2 和原则 3。
原则 2：树结点区间与查询区间不相交时，无视树结点的信息。原则 3：树结点区间包含查询区间内部时，保留树结点的信息。
第 3 步
最后，看一下右边子树，我们发现 [2, 3] 树结点区间包含查询区间，因此，需要使用原则 3。
第 4 步
那么最终，我们只选取两个树结点的信息，如下图所示：
那么我们可以得到区间 [1,3] 上的最小值：
min([1,1] 区间上的最小值，[2,3] 区间上的最小值) = 2
经过上面的查询，这里我总结了 3 个原则。
原则 1：区间相交的时候，需要拆分树结点区间，然后分别看左右子树。原则 2：树结点区间与查询区间不相交时，无视树结点的信息。原则 3：树结点区间包含查询区间内部时，保留树结点的信息。
3 个原则分别代表区间之间的三种关系。你不需要去死记这个关系，只需要注意以下两点：
树中的结点的区间会不停地拆分；
查询区间一直固定不变。
2. 查询的本质
似乎让你单纯地记录这个查询流程太枯燥了，因此我们还需要更深入地去想一下线段树查询的本质，理解之后再去记忆就比较简单了。你可以这样想，给定一个二叉树，然后又给了一个查询区间，那么可以把查询的过程表示成 2 步。
第 1 步：裁剪
我们修剪一下这棵二叉树，让所有的叶子结点都在查询区间范围内。
需要注意的是，当区间 [2,3] 已经包含查询区间的时候，其子树上的结点就没有必要保留了。最终，我们将灰色的树结点都去掉，只保留：1） “包含”查询区间的叶结点；2）根结点到这些叶结点的路径。
第 2 步：收集叶子结点的信息
当裁剪完成之后，只需要再查看存留的二叉树的叶结点信息就可以了。
不过我们这里并不真正地去裁剪这棵二叉树，而是在遍历的时候，只提取出相应的信息（区间上的最小值）即可。
下面是一道关于二叉树的裁剪的练习题，希望你可以尝试解决一下。
练习题 1： 给你二叉搜索树的根结点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使所有结点的值在 [low, high] 中。修剪树不应该改变保留在树中的元素的相对结构（如果没有被移除，原有的父代子代关系都应当保留）。可以证明，存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根结点。注意，根结点可能会根据给定的边界发生改变。
输入如下所示的二叉搜索树，并且 low = 1，high = 3。
输出：
代码：Java/C++/Python
完成练习题之后，你可以想一下，线段树查询与练习题 1 的裁剪有什么异同点？可以把你的思考写在留言区，我们一起讨论。
3. 线段树的更新
虽然这道题没有用到线段树的更新，但是面试的时候你可能会用到，所以我们还是要讲一下，
当我们要更新某个区间上的值时，需要将线段树路径上所有的点的区间信息都更新掉（更新的时候，采用后续遍历即可），如下图所示：
4. 线段树的存储
可能现在你准备开始用包含左右指针的二叉树写线段树了，不过还有更高效的方式——用数组表示一棵二叉树。
你可以回忆一下，“03 | 优先级队列：堆与优先级队列，筛选最优元素”学习堆的时候，我们已经用过一个数组来表示二叉树了，如下图所示：
这里也可以用数组来表示线段树，主要是因为：
数组具有更好的内存连续性；
内存连续性对 CPU 缓存更友好；
对 CPU 缓存更友好的数据结构能够运行得更快。
但是，通常我们学习的二叉树表示，会不停地 new TreeNode() 导致内存特别碎片化，因此对 CPU 缓存并不友好，导致运行得变慢。
当给定一个数组的时候，我们需要利用这个树创建一个线段树。根据线段树的定义：
根结点记录整个数组的信息；
左子树记录数组左半部分的信息；
右子树记录数组右半部分的信息。
这里我们可以肯定的是，根结点的信息，实际上需要依赖左子树的信息，以及右子树的信息才能够生成的。所以，这个二叉树的创建肯定是一个后序遍历。
然后再根据数组表示二叉树的方法，有以下 3 种：
i 结点的父结点 par = (i-1)/2；
i 结点的左子结点 2 * i + 1；
i 结点的右子结点 2 * i + 2。
5. 线段树的模板代码
此时，我们可以写出线段树的模板代码了（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
// 表示线段树的数组treeArray[]
// 数组里面的值表示区间里面的最小值
private int[] treeArray = null;
private int leftNodePos(int rootPos) {
return (rootPos << 1) + 1;
}
private int rightNodePos(int rootPos) {
return (rootPos << 1) + 2;
}
// treeArray[rootPos] 将会记录数组[start, end]
// 这个区间上的信息。在本题中，信息为区间上的最小值
private void buildTree(int rootPos, int[] A, int start, int end) {
// 范围为空
if (start > end)
return;
// 如果区间：只有一个数
if (start == end) {
treeArray[rootPos] = A[start];
} else {
// 否则需要将区间分为两半
final int mid = start + ((end - start) >> 1);
buildTree(leftNodePos(rootPos), A, start, mid);
buildTree(rightNodePos(rootPos), A, mid + 1, end);
// 构建成功之后，需要利用左子树的信息和右子树的信息来
// 来更新 [start, end] rootNode 的信息
treeArray[rootPos] =
Math.min(treeArray[leftNodePos(rootPos)],
treeArray[rightNodePos(rootPos)]);
}
}
/**
* 查询区间[queryStart, queryEnd]这个区间上的最小值信息
*
* treeArray[rootPos]表示区间 [start, end]上的最小值。
* 可以把前面的三个参数看成
* class TreeNode {
* int val; <-- arg: treeArray[rootPos];
* int rangeStart; <-- arg: start
* int rangeEnd: <-- arg: end
* TreeNode left; <-- leftNodePos(rootPos);
* TreeNode right: <-- rightNodePos(rootPos);
* }
*/
private int queryTree(int rootPos, int start, int end,
int queryStart, int queryEnd) {
// 无效区间，返回最大值
if (start > end || queryStart > queryEnd) {
return Integer.MAX_VALUE;
}
// 原则1： 包含于查询区间内部
if (queryStart <= start && end <= queryEnd) {
return treeArray[rootPos];
}
// 原则2：不相交时，放弃区间信息，这里我们返回最大值
if (end < queryStart || queryEnd < start) {
return Integer.MAX_VALUE;
}
// 原则3：当相交的时候，需要将[start, end]进行拆分
// 由于我们建树的时候，都是平分，所以这里将区间也进行平分
final int mid = start + ((end - start) >> 1);
return Math.min(queryTree(leftNodePos(rootPos),
start, mid, queryStart, queryEnd),
queryTree(rightNodePos(rootPos),
mid + 1, end, queryStart, queryEnd));
}
// 当我们要更新数组中A[inx] = value的时候
// 线段树中存储的区间的信息，也是需要更新的
void updateTree(int rootPos, int start, int end,
int idx, int value) {
// 如果树中的结点不在我们的更新路径上
if (start > end || idx < start || idx > end) {
return;
}
// 如果已经找到了叶子结点
if (start == idx && idx == end) {
treeArray[rootPos] = value;
return;
}
// 这里后序遍历
// 如果是非叶子结点，那么
// 先更新左右子结点，再更新根结点
final int mid = start + ((end - start) >> 1);
// 更新左子树
updateTree(leftNodePos(rootPos), start, mid, idx, value);
// 更新右子树
updateTree(rightNodePos(rootPos), mid + 1, end, idx, value);
// 更新根结点
treeArray[rootPos] =
Math.min(treeArray[leftNodePos(rootPos)],
treeArray[rightNodePos(rootPos)]);
}
|
代码：Java/C++/Python
那么我们通过使用线段树，就写出求解的代码了，如下所示（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
// ... 并查集的模板代码....
public
int largestRectangleArea(int[] heights) {
final int N = heights == null ? 0 : heights.length;
treeArray = new int[N << 2];
buildTree(0, heights, 0, N - 1);
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
// rootPos = 0表示根结点
// [0, N-1]表示根结点代表：[0, N-1]这个区间上的最小值信息
final int minHeight = queryTree(0, 0, N - 1, i, j);
ans = Math.max(ans, minHeight * (j - i + 1));
}
}
return ans;
}
}
|
代码：Java/C++/Python
接下来，我们分析一下时间复杂度，一共会有 N x N 个区间需要查询，每次查询的时间复杂度为 O(lgN)，所以时间复杂度为 O(N2 lgN)，空间复杂度为 O(N)。
到这里，我们利用一些区间信息查找常用的手段进行了优化：
使用 ST 算法将时间复杂度优化到 O(N2)；
使用线段树将时间复杂度优化到O(N2 lgN)。
可是，这两种算法都还是会超时，接下来应该怎么办呢？
其实，真正面试的时候，你应该注意，一开始找到的题目特点是基于区间查询的方式，实际上就把优化的上限限定死了。一共有 N x N 个区间要查，无论查多快，时间复杂度都不会比 O(N x N) 更好。
这就意味着，一开始，我们破题的大方向就是错的。当然，在这里我是发扬了要把一个题的特点深挖到底的精神，在练习的时候可以这么操作。如果是在面试中，还没有走到使用 ST 算法，线段树，就应该尝试寻找题目的其他特点了。
特点 2：选与不选
首先，我们假设问题是有一个最优解的，而这个最优解肯定是原始数组的一个连续子数组。那么，对于数组中的元素而言，就存在 2 种可能：
被最优解选中
没有被最优解选中
但是，如果我们去讨论每个元素的选/不选，时间复杂度就会瞬间爆炸到 O(2N)。但是你先别着急放弃这个特点，我们决心把这个特点死磕到底。
接着看题目，由于最大矩形的制约因素是被选中区域的最小值制约的。那么当给定一个区域 [start, end] 的时候，对于这个区间里面的最小值而言，只有两种可能。
第一种可能：被最优解选中，此时解为 area = minHeight * (end - start + 1)。
第二种可能：没有被最优解选中，那么可以利用最小值，将区域切分为两半：
计算左边区域的最大矩形的面积；
计算右边区域的最大矩形的面积。
然后再取这两种可能的最大矩形面积。
我们发现，利用区间里面的最小值（选/不选），可以将区间切分为更小的区间。
此时，我们就可以使用分治算法了。
分治算法 1
根据前面的思路，我们可以写出分治的代码（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
// 这里得到一个区域里面的最大矩形面积
// 这个区间域为[b, e)
// 注意e是取不到的
private int getRangeMaxArea(int[] heights, int b, int e) {
// 如果为空区间
if (b >= e) {
return 0;
}
// 如果区间中只有一个元素
if (b + 1 == e) {
return heights[b];
}
// 如果有多个元素。那么找到范围里面的最小值
// 如果有多个最小值，那么我们就找离中心最近的那个，尽量把区域进行等分
int mid = b + ((e-b) >> 1);
int minIndex = b;
for (int i = b + 1; i < e; i++) {
if (heights[i] < heights[minIndex]) {
minIndex = i;
} else if (heights[i] == heights[minIndex]) {
// 多个最小值，那么谁离mid更近，我们用谁
if (Math.abs(mid - i) < Math.abs(mid - minIndex)) {
minIndex = i;
}
}
}
// 在使用 最小值 情况下的面积
int useMinIndexArea = heights[minIndex] * (e - b);
// 不用 minIndex 那么就会把区间分为两部分
int leftMaxArea = getRangeMaxArea(heights, b, minIndex);
int rightMaxArea = getRangeMaxArea(heights, minIndex + 1, e);
return Math.max(useMinIndexArea,
Math.max(leftMaxArea, rightMaxArea));
}
public int largestRectangleArea(int[] heights) {
final int N = heights == null ? 0 : heights.length;
return getRangeMaxArea(heights, 0, N);
}
}
|
代码：Java/C++/Python
复杂度分析：正常情况下，时间复杂度为 O(NlgN)，最差情况下，比如数组是一个已排序的数组，并且里面元素都不相同，那么时间复杂度会变为 O(N2)，空间复杂度为 O(lgN)。
【小结】这里你可以回想一下我们在“08 | 排序：如何利用合并与快排的小技巧，解决算法难题？”学习的排序技巧，原来我们学习快速排序的时候，会用“三路切分”将区间分为三部分。而在这里，我们是用最小值将区间切分成两半。
那么有没有办法可以进一步优化呢？我们可以看到，分治的核心代码如下（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
|
int mid = b + ((e - b) >> 1);
int minIndex = b;
for (int i = b + 1; i < e; i++) {
if (heights[i] < heights[minIndex]) {
minIndex = i;
} else if (heights[i] == heights[minIndex]) {
// 多个最小值，那么谁离mid更近，我们用谁
if (Math.abs(mid - i) < Math.abs(mid - minIndex)) {
minIndex = i;
}
}
}
|
这段代码本质就是在搜索一个区间里面的最小值。如果你还有印象，寻找一个区间的信息，我们可以得到如下信息：
ST 算法预处理时间复杂度 O(NlgN)，查询区间最小值 O(1)，空间复杂度 O(NlgN)；
线段树建树 O(NlgN)，查询区间最小值 O(lgN)，空间复杂度 O(N)。
下面我再给你留两个练习题，请你分别用这两个算法再优化一下分治算法。如果有什么疑问，可以写在留言区，我会逐一为你解答。
练习题 2：请使用 ST 算法优化分治算法。并且分析优化之后的时间/空间复杂度。
代码：Java/C++/Python
练习题 3：请使用线段树算法优化我们的分治算法，并且分析优化之后时间/空间复杂度。
代码：Java/C++/Python
分治算法 2
在前面的分治算法中，我们在切分数组的时候，采用了一个区域里面的最小值进行切分。在最差情况下（数组元素不同且有序），会得到 O(N2) 时间复杂度。
不知道你有没有想起我们切分数组的算法。
合并排序：切分的时候，直接从数组的中间开始切分。时间复杂度最差也为 O(NlgN)。
快速排序：切分的时候，采用数组中的随机值进行切分。时间复杂度最差也为O(N2)。
于是，我们可以得到一个结论。
我们在切分数组的时候：如果采用值进行切分，那么最差情况下的时间复杂度会掉到 O(N2)；如果采用中间的下标进行切分，那么时间复杂度为 O(NlgN)。
就这道题而言，如果我们想把分治算法变成 O(NlgN)，应该怎么办？相信你已经想到了方向，那就是切分的时候，采用下标进行切分。
到这里，我们已经可以写出伪代码了（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int getMaxRangeArea(int[] heights, int b, int e) {
if (b >= e) {
return 0;
}
// 如果只有一个元素
if (b + 1 == e) {
return heights[b];
}
// 用数组中间的那个元素将数组分为两半
final int mid = b + ((e - b) >> 1);
// 不包含中间这个元素的时候，那么就只能在这个元素的左边和右边寻找了
int leftMaxArea = getMaxRangeArea(heights, b, mid);
int rightMaxArea = getMaxRangeArea(heights, mid + 1, e);
// 如果一定要包含heights[mid]
// 求出containsMidIndexArea; <-- 那么这里怎么求?
return Math.max(containsMidIndexArea,
Math.max(leftMaxArea, rightMaxArea));
}
|
接下来，我们看一下问题的核心部分，当包含 heights[mid] 的时候，应该如何计算？共有两种情况。
Case 1：其他元素都比 heights[mid] 大，heights[mid] 成了短板。
Case 2：存在比 heights[mid] 小的元素，heights[mid] 只是参与一下。
关于这两种情况的处理， 核心代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int minHeight = heights[mid];
int containsMidIndexArea = minHeight;
int left = m - 1, right = m + 1;
while (left >= b || right < e) {
if (right >= e || left >= b && heights[left] >= heights[right]) {
minHeight = min(minHeight, heights[left]);
left--;
} else {
minHeight = min(minHeight, heights[right]);
right++;
}
final int tmp = minHeight * (right - left - 1);
containsMidIndexArea = max(containsMidIndexArea, tmp);
}
|
那么，到此为止，我们就可以写出完全是 O(NlgN) 的代码了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
private int getMaxRangeArea(int[] heights, int b, int e) {
if (b >= e) {
return 0;
}
// 如果只有一个元素
if (b + 1 == e) {
return heights[b];
}
// 用数组中间的那个元素将数组分为两半
final int mid = b + ((e - b) >> 1);
// 不包含中间这个元素的时候，那么就只能在这个元素的左边和右边寻找了
int leftMaxArea = getMaxRangeArea(heights, b, mid);
int rightMaxArea = getMaxRangeArea(heights, mid + 1, e);
// 如果一定要包含heights[mid]
// 那么就有两种情况。
int minHeight = heights[mid];
int containsMidIndexArea = minHeight;
int left = mid - 1, right = mid + 1;
while (left >= b || right < e) {
if (right >= e ||
left >= b && heights[left] >= heights[right]) {
minHeight = Math.min(minHeight, heights[left]);
left--;
} else {
minHeight = Math.min(minHeight, heights[right]);
right++;
}
final int tmp = minHeight * (right - left - 1);
containsMidIndexArea = Math.max(containsMidIndexArea, tmp);
}
return Math.max(containsMidIndexArea,
Math.max(leftMaxArea, rightMaxArea));
}
public int largestRectangleArea(int[] heights) {
final int N = heights == null ? 0 : heights.length;
return getMaxRangeArea(heights, 0, N);
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度 O(NlgN)，空间复杂度 O(1)（不算栈空间）。
【小结】在写这个算法的时候，我们需要注意两个地方。
其一：在处理 heights[mid] 的时候，将包含关系分为以下 2 种：
包含 heights[mid]，并且找到的区域内的元素都比 heights[mid] 大；
不包含 heights[mid]，这种情况需要递归处理 [b, mid) 和 [mid + 1, e)。
容易出错的地方在于，包含 heights[mid] 的时候，实际上有两种情况的（前面我们提到的Case 1 和 Case 2）。这里只处理了 Case 1，但是没有处理 Case 2。
其二：采用这种分治算法，包含 heights[mid] 的时候，采用了双指针的做法，left 和 right 分别向两边推进。但是你需要格外注意，推进的时候，哪边大，则移动哪边的指针。
你能想想为什么吗？请你完成下面的练习题 4，期待看到你理解与思考。
练习题 4：这里的分治算法在往左右两边推进的时候，为什么哪边大就往哪边移动呢？你能再想一下，这与“11 | 贪心：这种思想，没有模板，如何才能掌握它？”介绍的贪心算法的例 1 有什么异同吗？
特点 3：左右两边较小的数
构成一个矩形的面积的时候，有宽和高。无论是特点 1，还是特点 2，它们都有一个共同点：先固定矩形的宽，再去选择高。
有没有可能反过来呢？我们先去固定高度，再去决定宽度。当我们选择数组中的元素 heights[i] 作为矩形的高度时。寻找宽度需要满足以下两个条件：
i 元素必须要在这个范围内；
这个范围内的元素都必须要大于等于 heights[i]。
那么我们就可以称 heights[i] 决定了这个最大范围的面积。
小于我的位置
那么这也就意味着，我们需要解决如下的问题。
数组中元素右边离我最近且比我小的元素的位置
代码：Java/C++/Python
数组中元素左边离我最近且比我小的元素的位置
代码：Java/C++/Python
实际上，这两个问题，我们已经在“01 | 栈：从简单栈到单调栈，解决经典栈问题”介绍单调栈时学过了。那么你现在解决起来，应该是很容易了吧。本讲不再过多叙述，直接给出如下代码（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
class LeftSmall
{
// 当我们要找左边比我小的元素的时候，需要用递增栈
public static int[] findLeftSmall(int[] A)
{
if (A == null || A.length == 0) {
return new int[0];
}
// 结果数组
int[] ans = new int[A.length];
// 注意，栈中的元素记录的是下标
Stack<Integer> t = new Stack<>();
// 注意这里的遍历方向发生了变化，因为我们是要找到左边比我小的元素的位置
for (int i = A.length - 1; i >= 0; i--) {
final int x = A[i];
// 每个元素都遍历栈中的元素完成消除动作
// 这里是递减栈
// 如果发现进来的元素x与栈中元素相比
// 如果大于栈中的元素，那么要把栈中的元素弹出去
while (!t.empty() && A[t.peek()] > x) {
// 消除的时候，记录一下被谁消除了
ans[t.peek()] = i;
// 消除时候，值更大的需要从栈中消失
t.pop();
}
// 剩下的入栈
t.push(i);
}
// 栈中剩下的元素，由于没有人能消除他们，因此，只能将结果设置为-1。
while (!t.empty()) {
ans[t.peek()] = -1;
t.pop();
}
return ans;
}
}
class RightSmall
{
public static int[] findRightSmall(int[] A)
{
// 结果数组
int[] ans = new int[A.length];
// 注意，栈中的元素记录的是下标
Stack<Integer> t = new Stack<>();
for (int i = 0; i < A.length; i++) {
final int x = A[i];
// 每个元素都向左遍历栈中的元素完成消除动作
while (!t.empty() && A[t.peek()] > x) {
// 消除的时候，记录一下被谁消除了
ans[t.peek()] = i;
// 消除时候，值更大的需要从栈中消失
t.pop();
}
// 剩下的入栈
t.push(i);
}
// 栈中剩下的元素，由于没有人能消除他们，因此，只能将结果设置为-1。
while (!t.empty()) {
ans[t.peek()] = -1;
t.pop();
}
return ans;
}
}
class Solution
{
public int largestRectangleArea(int[] A)
{
final int N = A == null ? 0 : A.length;
int[] leftSmall = LeftSmall.findLeftSmall(A);
int[] rightSmall = RightSmall.findRightSmall(A);
int ans = 0;
for (int i = 0; i < N; i++) {
final int height = A[i];
// 左边比我小的位置
// 右边比我小的位置
final int leftPos = leftSmall[i];
final int rightPos = rightSmall[i] == -1 ? N : rightSmall[i];
// 现在我们确定区间(leftPos, rightPos)
// 注意两边都是开区间。在这个区间里面，所有的数肯定都是 >= A[i]的。
// 那么底部的宽度就是
final int width = rightPos - leftPos - 1;
final int area = height * width;
ans = Math.max(ans, area);
}
return ans;
}
}
|
代码：Java/C++/python
复杂度分析：时间复杂度 O(N)，空间复杂度 O(N)。
【小结】如果你看到这里，突然感觉代码都很神奇，充满了魔法，就是时候温习一下“01 | 栈：从简单栈到单调栈，解决经典栈问题”中单调栈的“魔法技能”部分了。通过复习有时候也能唤醒你算法的巨龙哦。
单调栈的性质
我们来看递增栈（不是严格递增），栈中元素存放的是数组 A[] 的下标。如下图所示：
说明：在这个图中，左边是栈底，右边是栈增长的方向。栈中不同的矩形表示相应 A[] 数组中下标位置相应值的大小。那么，首先基于递增栈的定义，我们可以知道它有如下特性：
栈中存放的下标，如果 i 在 j 之前入栈，那么必然满足 A[i] <= A[j]。
“削”的定义：当需要把一个更小的元素入栈的时候，这个更小的元素就会把栈中大的元素出栈，直到栈为空，或者栈顶元素更小，再入栈。
例如：当栈中已经有 <i, j>，现在需要将 A[k] 入栈，但是 A[i] < A[k] && A[k] < A[j]。那么 A[k] 就会把 A[j] 削出栈。如下图所示：
根据这个特性，我们肯定可以得到 A[i] <= A[k] < A[j]。基于这个特性，还可以得出 3 个有用的性质。
性质 1
如下图所示：
假设 i, j 这两个下标在单调栈中相邻，那么在原数组 A[] 中， (i, j) 这个开区间里面的数都大于 A[j]。
这里我们采用反证法来证明这个性质。首先给出反证法的条件：
单调栈中连续存放着下标 i, j（但并不代表下标 i,j 是连续的，也就是说 i + 1 不一定等于j）；
假设 A[] 数组在 (i, j) 范围中存在 1 个下标 k，即 i < k < j，并且使得 A[k] < A[j] 成立。
证明：如果 A[k] < A[j]，那么将 A[k] 放入单调队列之后，由于 (k, j) 范围里面的数组都大于 A[j]。那么当 A[j] 入栈之后，应该位于 A[k] 之后。于是栈中会形成 <i, k, j> 三个数。但实际上栈中只存放了 <i, j> 两个数，并且 i < k < j，这里存在矛盾。所以在 (i, j) 这个开区间范围里面的数，都必须大于 A[j]。
之所以这些大于 A[j] 的元素没有出现在栈中，是因为这些元素在 A[j] 入栈时可能都在栈中，但是立马都被 A[j] 削出栈了。
性质 2
然后，基于性质 1，当单调栈中有 <i, j, k>3 个原数组的下标。那么可以得到性质 2：
当单调栈中有 <i, j, k> 3 个数组下标时，其中 (i, k] 这个范围里面的元素，肯定 >= A[j]。
证明如下：
根据性质 1，可以得到 (i, j) 里面的元素都大于 A[j]，即 A[(i,j)] > A[j]；
根据性质 1，还可以得到 (j, k) 里面的元素都大于 A[k]，即 A[(j,k)] > A[k]；
由于 j 在 k 之前入栈，所以可以肯定 A[j] <= A[k]。
综上，A[(j,k)] > A[k] >= A[j]，所以可以得出结论 (i, k] 里面的元素肯定 >= A[j]。
性质 3
现在我们遇到下面这种场景。在单调栈中，已经存放了原数组的两个下标 <i, j>，其中 j 是栈顶元素，现在要把一个更小的值 A[k] 对应的下标 k 入栈。如下图所示：
此时，根据单调栈的性质，需要将 A[j] 弹出栈（有可能 A[k] 已经削除了栈中的很多元素，现在轮到削除 A[j] 了）。那么此时我们可以得到一个性质 3：
原数组 (j, k) 范围里面的数，都大于 A[j]。
同样，我们可以采用反证法。先给出反证法的条件：
当 k 要入栈时，单调栈中连续存放着下标 i, j（但并不代表下标 i,j 是连续的，也就是说 i + 1 不一定等于 j）；
假设范围 (j, k) 中存在1 个下标 x；
使得 A[x] <= A[j] 成立。
如果有 j < x < k，并且 A[x] <= A[j] 成立，那么单调栈中现在必然存在 A[x] 元素。但是现在栈中存放着 A[j]，并且没有 A[x] 元素。所以得出矛盾。所以性质 3 成立。
其实性质 2 和性质 3 有个比较好记的地方。如果你将范围 (i,j), (j, k) 看成两个“空档”。那么 A[j] 就好像总是挑着两座大山，如下图所示：
至于 A[j] 和 A[k] 值的大小，当然是比较容易判断的：
如果栈中 j 在 k 之前（且相邻），那么 A[j] < A[k]；
如果 A[k] 要削 A[j] 出栈，那么 A[k] < A[j]。
到这里，我们就可以写出代码了（解析在注释里）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
public int largestRectangleArea(int[] A) {
final int N = A == null ? 0 : A.length;
// 虽然可以用Stack<Integer>，但是这里我们为了更快地操作，我们用
// 数组模拟栈来运行，因为我们知道最多存放的内容实际上就是N个
int top = 0;
// s[top-1]表示栈顶元素
int[] s = new int[N];
int ans = 0;
// 注意，这里我们取到了i == N
// 按理说，不应该取到i == N的。但是这时候，主要是为了处理这种数组
// A = [1, 2, 3]
// 没有任何元素会出栈。
// 那么最后我们用一个0元素，把所有的元素都削出栈。
// 这样代码就可以统一处理掉。
for (int i = 0; i <= N; i++) {
// 注意：当i == N的时候，x = -1;
// 比数组中的元素都要小。
final int x = i == N ? -1 : A[i];
while (top > 0 && A[s[top - 1]] > x) {
// 计算以A[s[top]]的元素的高度的矩形。
final int height = A[s[--top]];
// i元素要将index = s[top-1]的元素出栈。
// 那么根据性质2/3：
// 此时A[s[top-1] .... i) 这个区间里面的元素都是
// 大于A[s[top-1]]的
final int rightPos = i;
// 这里需要使用性质1.
// 注意：当栈中一个元素都没有的时候，要取-1
final int leftPos = top > 0 ? s[top - 1] : -1;
final int width = rightPos - leftPos - 1;
final int area = height * width;
ans = Math.max(ans, area);
}
s[top++] = i;
}
return ans;
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度 O(N)，空间复杂度 O(N)。
DP
前面我们使用单调栈来求解一个左右两边第一个较小的元素的位置。现在我们重新来考虑一下这个问题。
题目：数组中左边离我最近且比我小的元素的位置。
我们在考虑的时候，直接考虑最后一个元素的情况（不知道你是否还记得我们DP 的最后一步），也就是求解 A[k+1] 左边第一个比较小元素的位置。假设 [0, k] 这个范围元素的解都放在 dp[] 数组里面。如果我们要求 A[k+1] 左边第一个比较小元素的位置。通常的写法如下：
1
2
3
4
5
6
|
for (int pre = k; pre >= 0; pre--) {
if (A[pre] < A[k+1]) {
dp[k+1] = pre;
break;
}
}
|
但是这么写，时间复杂度就变成 O(N)。如果要求解“数组中元素左边离我最近且比我小的元素的位置”，问题就秒变 O(N2)。而我们知道，如果使用单调栈，是可以在 O(N) 时间复杂度解决的。
我们立马会发现，求解 A[k+1] 的时候，还没有用上 dp[] 数组。那么我们可以这样操作：
首先 A[k] 与 A[k+1] 比较，如果 A[k] >= A[k+1]，那么直接跳到下标 j = dp[k] 这个位置；
重复上述步骤，直到找到一个元素比 A[k+1] 小，或者没有任何元素为止。
通过这样的方式，我们可以快速跳过一些元素，使时间复杂度变为 O(lgN)。于是代码可以长成这样：
1
2
3
4
5
|
int pre = k + 1 - 1;
while (pre != -1 && A[pre] >= A[k+1]) {
pre = dp[pre];
}
dp[k+1] = pre;
|
联想 1：你可以想一下，这和 KMP 算法有没有什么相似的地方？联想 2：你可以再想一下，这和我们学过的并查集有没有什么相似的地方？
那么我们的求解最大矩形的代码，就可以利用这个思想，写出代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public int largestRectangleArea(int [] A) {
final int N = A == null ? 0 : A.length;
if (N == 0) {
return 0;
}
int[] lm = new int[N]; // left min的位置
int[] rm = new int[N]; // right min的位置
lm[0] = -1;
for (int i = 1; i < N; i++) {
int idx = i - 1;
while (idx != -1 && A[idx] >= A[i]) {
idx = lm[idx];
}
lm[i] = idx;
}
rm[N - 1] = N;
for (int i = N - 2; i >= 0; i--) {
int idx = i + 1;
while (idx != N && A[idx] >= A[i]) {
idx = rm[idx];
}
rm[i] = idx;
}
int ans = 0;
for (int i = 0; i < N; i++) {
ans = Math.max(ans, A[i] * (rm[i] - lm[i] - 1));
}
return ans;
}
}
|
代码：Java/C++/Python
复杂度分析：时间复杂度 O(NlgN)，时间复杂度可以类比并查集的跳跃方式，空间复杂度 O(N)。
总结
在这一讲里面，我们采用的总方针是：
深挖题目的特点；
对标数据结构/算法特点；
将特点进行结合，创造出新的解法。
我们再将本讲介绍的题目进行一个总结和归纳，如下图所示：
思考题
这里我再给你留了一下思考题：给定一个仅包含
0
和
1
、大小为
rows x cols
的二维二进制矩阵，找出只包含
1
的最大矩形，并返回其面积。
代码：Java/C++/Python
关于最大矩形这一道题，我们就介绍到这里。如果你发现这个题目还有新的特点，还能匹配到新的算法，那么有可能你还会发现新的解法哦。接下来我们将进入 17 | 深度思考子集：如何掌握 5 种通用解法？记得按时来探险。
-– ### 精选评论