16 | 如何利用 DP 与单调队列寻找最大矩形？

数据结构与算法面试宝典 - 前微软资深软件工程师 - 拉勾教育

面试的场景与我们之前学习某个知识点的情况不再相同。在学习 “一解多题” 的时候，由于已经预设了前提，实际上我们是知道某个题会用到什么知识点的。

但是在面试中，当你拿到一个题目，可能一时想不到具体采用哪种解法。所以在本讲，我将带你回到面试场景，教你分析题目的思路。我们的目标就变成从题目出发，去考虑如何破解一个题。

本讲将会重点学习：

• 如何挖掘题目的特点
• 如何利用特点匹配到数据结构和算法知识点

完成这两步动作，需要你熟练地掌握前面 “一解多题” 模块介绍的数据结构与算法知识点。养兵千日，用在一时，是时候派上用场了。

最大矩形

【题目】给定一个数组，里面有n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入：[2,1,5,6,2,3]

输出：10

解释：柱状图的示例，其中每个柱子的宽度为 1，给定的高度为[2,1,5,6,2,3]。

输入 最大矩形

暴力算法

当拿到题目之后，一种最简单、最暴力的算法立马会出现在我们脑海里面。那就是：

• 分别选定两个柱子，然后计算这两个柱子为边界，构成的最大矩形的面积；
• 取出所有的矩形面积中的最大面积。

那么根据这个思路，可以得到代码如下：

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 的子区间的最小值，再从中选择最小的即可。

区间[start, end]上的最小值 = min(区间[l, l+2<sup>p</sup>)上的最小值
                         区间[r-2<sup>p</sup>+1, r]上的最小值)

基于结论 1，我们可以得到结论 2。

计算顺序：

1. 先计算出长度为 20 的所有区间的最小值；
2. 再计算长度为 21 的所有区间的最小值；
3. 然后计算长度为 22 的所有区间的最小值；
4. 直到长度为 2x 的区间的最小值。

其中 2x 刚好大于等于给定的数组长度。

2. 指数表示法

当拆分完成之后，原本一个区间的表示是 [start, end]，分为两个长度（len）一样的区间。更进一步，这两个区间可以表示为 , 。

例 1 中 [10, 18] 拆分之后，可以表示为 , 。

例 2 中 [10, 17] 拆分之后，可以表示为 , 。

重新表示之后，区间 中，由于长度信息 len 总是 2p，因此我们可以只记录指数 p。

例 1 中 [10, 18] 拆分之后，可以表示为 , 。

例 2 中 [10, 17] 拆分之后，可以表示为 , 。

如果我们将区间采用指数 p 表示之后，就只需要使用空间 st[N][log2(N)+1]，也就是空间复杂度为 O(NlgN)。

那么基于以上两个核心思想，我们可以写出 ST 算法的代码了。这里可以分为两步，一步是预处理，另一步是查询。

预处理构建 st[][] 数组代码如下：

void buildST(int[] A, int[][] st) {
final int N = A == null ? 0 : A.length;
for (int i = 0; i < N; i++) {
    st[i][0] = A[i];
  }
for (int j = 1; (1 << j) <= N; j++) {
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]);
    }
  }
}

查询阶段的代码如下：

int minHeight(int[][] st, int l, int r)
{
int len = r - l + 1;
int j = log2(len);
return Math.min(st[l][j], st[r - (1 << j) + 1][j]);
}

需要注意的是，在查询阶段，如果一个区间的长度本来就是 2p，那么就可以拆分成两个完全重合的区间。

得到 ST 算法的代码之后，我们就可以开始解决这道题目了。代码如下：

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;
for (int i = 0; i < N; i++) {
            st[i][0] = A[i];
        }
for (int j = 1; (1 << j) <= N; j++) {
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) {
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. 线段树的模板代码

此时，我们可以写出线段树的模板代码了（解析在注释里）：

private int[] treeArray = null;
private int leftNodePos(int rootPos) {
return (rootPos << 1) + 1;
}
private int rightNodePos(int rootPos) {
return (rootPos << 1) + 2;
}
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);
        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;
    }
if (queryStart <= start && end <= queryEnd) {
return treeArray[rootPos];
    }
if (end < queryStart || queryEnd < start) {
return Integer.MAX_VALUE;
    }
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));
}
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

那么我们通过使用线段树，就写出求解的代码了，如下所示（解析在注释里）：

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++) {
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

根据前面的思路，我们可以写出分治的代码（解析在注释里）：

class Solution {
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]) {
if (Math.abs(mid - i) < Math.abs(mid - minIndex)) {
                    minIndex = i;
                }
            }
        }
int useMinIndexArea = heights[minIndex] * (e - b);
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 | 排序：如何利用合并与快排的小技巧，解决算法难题？”学习的排序技巧，原来我们学习快速排序的时候，会用 “三路切分” 将区间分为三部分。而在这里，我们是用最小值将区间切分成两半。

那么有没有办法可以进一步优化呢？我们可以看到，分治的核心代码如下（解析在注释里）：

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]) {
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)，应该怎么办？相信你已经想到了方向，那就是切分的时候，采用下标进行切分。

到这里，我们已经可以写出伪代码了（解析在注释里）：

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);
return Math.max(containsMidIndexArea,
                    Math.max(leftMaxArea, rightMaxArea));
}

接下来，我们看一下问题的核心部分，当包含 heights[mid] 的时候，应该如何计算？共有两种情况。

• Case 1：其他元素都比 heights[mid] 大，heights[mid] 成了短板。
• Case 2：存在比 heights[mid] 小的元素，heights[mid] 只是参与一下。

关于这两种情况的处理， 核心代码如下：

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) 的代码了。

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);
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 | 栈：从简单栈到单调栈，解决经典栈问题” 介绍单调栈时学过了。那么你现在解决起来，应该是很容易了吧。本讲不再过多叙述，直接给出如下代码（解析在注释里）：

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];
while (!t.empty() && A[t.peek()] > x) {
        ans[t.peek()] = i;
        t.pop();
      }
      t.push(i);
    }
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);
    }
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];
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]。

“削”的定义：当需要把一个更小的元素入栈的时候，这个更小的元素就会把栈中大的元素出栈，直到栈为空，或者栈顶元素更小，再入栈。

例如：当栈中已经有 ，现在需要将 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) 这个开区间范围里面的数，都必须大于 A[j]。

之所以这些大于 A[j] 的元素没有出现在栈中，是因为这些元素在 A[j] 入栈时可能都在栈中，但是立马都被 A[j] 削出栈了。

性质 2

然后，基于性质 1，当单调栈中有 3 个原数组的下标。那么可以得到性质 2：

当单调栈中有 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

现在我们遇到下面这种场景。在单调栈中，已经存放了原数组的两个下标 ，其中 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]。

到这里，我们就可以写出代码了（解析在注释里）：

class Solution {
public int largestRectangleArea(int[] A) {
final int N = A == null ? 0 : A.length;
int top = 0;
int[] s = new int[N];
int ans = 0;
for (int i = 0; i <= N; i++) {
final int x = i == N ? -1 : A[i];
while (top > 0 && A[s[top - 1]] > x) {
final int height = A[s[--top]];
final int rightPos = i;
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] 左边第一个比较小元素的位置。通常的写法如下：

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)。于是代码可以长成这样：

int pre = k + 1 - 1;
while (pre != -1 && A[pre] >= A[k+1]) {
    pre = dp[pre];
}
dp[k+1] = pre;

联想 1：你可以想一下，这和 KMP 算法有没有什么相似的地方？
联想 2：你可以再想一下，这和我们学过的并查集有没有什么相似的地方？

那么我们的求解最大矩形的代码，就可以利用这个思想，写出代码如下：

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]; 
int[] rm = new int[N]; 
        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 种通用解法？记得按时来探险。