博文中会简要介绍Leetcode P0084题目分析及解题思路。
“Largest Rectangle in Histogram”是一道很经典的难题。这道题主要有两种思路，一种是利用单调栈；另一种是分而治之，利用线段树。
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
首先讲解使用单调栈的解法。单调栈，指的是栈内元素的大小关系保持单调，可以是单调上升（不递减）或者是单调下降（不递增）。其实在p0042里我们使用过一次单调栈，不过利用单调栈的解法并没有细讲。在p0042中我们使用的栈是单调下降的，但是在本题里我们使用的栈则是单调上升的。
为什么这道题会想到利用单调栈？
我们需要从求解矩形面积出发。在这道题里，以某个区域为边的矩形面积取决于这个区域内的最短直方形的高度。而如果我们观察任意一个区域中的直方形，不难发现由这个直方形的高度形成的最大矩形面积取决于这个直方形左右侧第一个比其低的坐标差。换言之，如果一段区域内直方形是单调上升（单调不递减）的，我们无法计算出由这个区域内某个直方形的高度形成的最大矩形面积，直到一个更低的直方形来约束这个矩形的边长（碰到边界其实也可以理解为碰到高度为0的直方形）。
据此可知，通过维护一个单调上升的单调栈，当遍历到的当前直方形高度小于等于栈顶元素的高度时，我们可以计算由栈内直方形构成的最大矩形面积，直到栈顶元素的高度比当前遍历到的直方形高度更低。具体的思路可以参考下述代码中的注释。
以下是Java的题解代码实现。
class Solution {
public int largestRectangleArea(int[] heights) {
int N = heights.length;
if (N == 0)
return 0;
Deque<Integer> stack = new LinkedList<>();
int maxRect = 0, top = -1, rect = 0;
// 直方图的区域边界，可以认为代表了一个高度为0的直方形
stack.offerFirst(-1);
// 遍历直方图内每个直方形
for (int itr=0; itr<N; ++itr) {
// 获取栈顶直方形的坐标
top = stack.peekFirst();
// 如果栈顶不是边界并且栈顶直方形的高度不低于当前遍历到的直方形高度，则不断从栈顶弹出直方形，并计算由当前直方形构成的最大矩形面积
while ((top = stack.peekFirst()) != -1 && heights[top] >= heights[itr]) {
top = stack.pollFirst();
// 我们知道由这个直方形的高度形成的最大矩形面积取决于这个直方形左右侧第一个比其低的坐标差，而这个栈是单调上升的，所以这个直方形左侧一定是一个比它低的直方形
// 所以这个矩形的两条边分别为这个直方形的高度和当前遍历的下标与左侧直方形的下标的差-1
rect = (itr-stack.peekFirst()-1)*heights[top];
maxRect = Math.max(maxRect, rect);
}
stack.offerFirst(itr);
}
// 最后统计栈内剩余的直方形构成的矩形面积，这些直方形的右边界是整个直方图的右边界
while (stack.size() > 1) {
top = stack.pollFirst();
rect = (N-stack.peekFirst()-1)*heights[top];
maxRect = Math.max(maxRect, rect);
}
return maxRect;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int N = heights.size();
if (N == 0)
return 0;
stack<int> bar_stack;
int max_rect = 0, rect = 0, top = -1;
bar_stack.push(-1);
for (int itr=0; itr<N; ++itr) {
while ((top = bar_stack.top()) != -1 && heights[top] >= heights[itr]) {
bar_stack.pop();
rect = heights[top]*(itr-bar_stack.top()-1);
max_rect = max(max_rect, rect);
}
bar_stack.push(itr);
}
while ((top = bar_stack.top()) != -1) {
bar_stack.pop();
rect = heights[top]*(N-bar_stack.top()-1);
max_rect = max(max_rect, rect);
}
return max_rect;
}
};
第二种解法利用了分而治之的思想。我们不难发现，对于任意一个区域而言，以这个区域的长度为边的最大矩形面积取决于这个区域内的最小直方形高度。换言之，对于任意一个区域的最大矩形面积，应当取决于这个区域内最小直方形高度和这个最小直方形左右区域的最大矩形面积。这样的思路就形成了一个递归，于是我们可以利用分而治之的思想，每次得到区域内的最低直方形的坐标pivot，计算出以pivot这个直方形构成的最大矩形面积，然后以pivot为界获取左右区域的最大矩形面积，然后取三者中的最大值。
虽然分而治之的解法的平均时间复杂度为O(nlogn)，但是其最坏时间复杂度是O(n^2)。譬如一个所有直方形高度相同的直方图，分治的时候，总是将当前区域[l,r]分成[l,r-1]和[r,r]。为了能够保持O(nlogn)的时间复杂度不退化，我们需要使用线段树来辅助。
线段树的一个重要的特性就是区间查询和区间修改的时间复杂度是O(logn)。这道题我们会利用其区间查询的特性，也就是给定一个区间[l,r]，查询这个区间的信息需要的时间是O(logn)的。线段树的具体定义和实现可以参考OI Wiki 线段树。
以下是利用分而治之思想和线段树的C++题解代码实现。
class SegTreeNode {
public:
int start;
int end;
int min;
SegTreeNode *left;
SegTreeNode *right;
SegTreeNode(int start, int end) {
this->start = start;
this->end = end;
left = right = NULL;
}
};
class Solution {
public:
int largestRectangleArea(vector<int> &heights) {
// First build a segment tree
SegTreeNode *root = _BuildSegmentTree(heights, 0, heights.size()-1);
// Next calculate the maximum area recursively
return _MaxRect(heights, root, 0, heights.size()-1);
}
private:
int _MaxRect(vector<int> &heights, SegTreeNode* root, int left, int right) {
if (left >= right)
return (left > right)? 0: heights[left];
int pivot = _Query(root, heights, left, right);
int rect = heights[pivot]*(right-left+1);
return max(rect,
max(_MaxRect(heights, root, left, pivot-1),
_MaxRect(heights, root, pivot+1, right))
);
}
SegTreeNode *_BuildSegmentTree(vector<int> &heights, int left, int right) {
if (left > right)
return nullptr;
SegTreeNode *root = new SegTreeNode(left, right);
if (left == right) {
root->min = left;
}
else {
int mid = (left+right)/2;
root->left = _BuildSegmentTree(heights, left, mid);
root->right = _BuildSegmentTree(heights, mid+1, right);
root->min = (heights[root->left->min] > heights[root->right->min])? root->right->min: root->left->min;
}
return root;
}
int _Query(SegTreeNode *root, vector<int>& heights, int left, int right) {
// [left,right]为查询区间, [start,end]为当前节点包含的区间, root为当前节点
if (root == NULL || right < root->start || left > root->end)
return -1;
// 当前区间为询问区间的子集时直接返回当前区间的min
if (left <= root->start && right >= root->end) {
return root->min;
}
int mid = (root->start+root->end)/2, left_min = -1, right_min = -1;
// 如果左孩子代表的区间[start,mid]与询问区间[left,right]有交集, 则递归查询左孩子
if (left <= mid) {
left_min = _Query(root->left, heights, left, right);
}
// 如果右孩子代表的区间[mid+1,end]与询问区间[left,right]有交集, 则递归查询右孩子
if (right > mid) {
right_min = _Query(root->right, heights, left, right);
}
// 如果其中一个孩子结点返回-1，则取非-1的那个孩子结点值返回
if (left_min == -1 || right_min == -1)
return max(left_min, right_min);
return (heights[left_min] > heights[right_min])? right_min: left_min;
}
};