1. 题目描述
2. 样例输入
- Input: [2,1,5,6,2,3]
- Output: 10
3. 解题报告
解法一: 暴力搜索法
我们自然而然就会想到的最朴素的解法就是用双重嵌套 for 循环来暴力搜索最优解, 第一层 for 循环遍历每一个 bar, 第二层 for 循环遍历以上一层 for 循环中每一个 bar 为最右端再向左看的所有可能的矩形, 在此过程中记录最大矩形的值即可.
代码如下:
- public static int largestRectangleArea(int[] heights) {
- int res = 0;
- int curHeight = 0;
- for (int i = 0; i <heights.length; ++i) {
- curHeight = heights[i];
- for (int j = i; j>= 0; --j) {
- curHeight = Math.min(curHeight, heights[j]);
- res = Math.max(res, curHeight * (i - j + 1));
- }
- }
- return res;
- }
运行结果如下:
显然, 暴力搜索效率很低, 其时间复杂度为 O(n2), 只打败了 10% 的人, 这种成绩是不可接受的, 我们要考虑优化算法.
解法二: 暴力搜索法 + 剪枝
暴力搜索法存在很多重复计算, 经过简单观察, 可以发现, 其实我们没有必要在每一个 bar 都回头向左遍历一遍所有可能的矩形, 我们只需要在局部峰值处回头向左遍历即可. 所谓局部峰值, 即当 heights[i]>heights[i+1] 时, 我们就认为 heights[i] 为局部峰值. 这样做的原因是因为非局部峰值处的情况后面的局部峰值都可以包括. 举个例子, 观察直方图 [2,1,5,6,2,3], 局部峰值为 [2,6,3], 非局部峰值 5 所能包含的矩形在局部峰值 6 处都可以包括并且可以加上 6 本身的一步分组成更大的矩形, 所以就没必要计算非局部峰值处的情况了, 读者画个图将更有助于理解.
代码如下:
- public static int largestRectangleArea(int[] heights) {
- int res = 0;
- int curHeight = 0;
- for (int i = 0; i <heights.length; ++i) {
- if (i < heights.length - 1 && heights[i] <= heights[i + 1]) {
- continue;
- }
- curHeight = heights[i];
- for (int j = i; j>= 0; --j) {
- curHeight = Math.min(curHeight, heights[j]);
- res = Math.max(res, curHeight * (i - j + 1));
- }
- }
- return res;
- }
运行结果如下:
由上图可见, 速度有了显著提升, 打败了 90% 的人也算是差强人意, 这效果虽好但理论上仍然是 O(n2) 的复杂度, 我们接下来寻求时间复杂度更低的解法.
解法三: 分治法
其实对于优化暴力搜索法, 最容易想到的方法并不是解法二中的剪枝法, 那是需要一些灵感的. 按照解题套路, 接下来我们应该尝试是否有时间复杂度为 O(nlgn) 的解法, 一看到 lgn, 我们应该本能反应到是否可以尝试一下分治法. 使用分治法解决此题的思路还是很清晰的: 对于一段给定数量的 bar, 从中间的 bar 一分为二, 含有最大矩形面积的区域要么在中间 bar 的左侧, 要么在中间 bar 的右侧, 要么是横跨中间 bar. 对于横跨中间 bar 的情况, 可以在 O(n) 时间内解决, 因此, 递归式为 T(n)=2T(n/2)+O(n), 时间复杂度为 O(nlgn).
代码如下:
- public static int maxArea(int[] heights, int l, int h) {
- if (l == h) return heights[l];
- int m = l + (h - l) / 2;
- int res = maxArea(heights, l, m);
- res = Math.max(res, maxArea(heights, m + 1, h));
- res = Math.max(res, combineArea(heights, l, m, h));
- return res;
- }
- public static int combineArea(int[] heights, int l, int m, int h) {
- int res = 0;
- int i = m, j = m + 1;
- int curHeight = Math.min(heights[i], heights[j]);
- while (i>= l && j <= h) {
- curHeight = Math.min(curHeight, Math.min(heights[i], heights[j]));
- res = Math.max(res, (j - i + 1) * curHeight);
- if (i == l) {
- ++j;
- } else if (j == h) {
- --i;
- } else {
- if (heights[i - 1]> heights[j + 1]) {
- --i;
- } else {
- ++j;
- }
- }
- }
- return res;
- }
- public static int largestRectangleArea(int[] heights) {
- if (heights.length == 0) return 0;
- else return maxArea(heights, 0, heights.length - 1);
- }
运行结果如下:
速度基本符合预期, 但是否还存在 O(n) 的解法呢?
解法四: 单调栈法
所谓单调栈, 就是栈内只存放单调递增或单调递减的序列, 以单调增栈为例, 若待入栈元素比栈顶元素大, 则入栈; 反之, 则弹出栈顶元素, 进行相应处理. 使用单调栈可以找到元素向左遍历第一个比他小的元素, 也可以找到元素向左遍历第一个比他大的元素. 单调栈的维护是 O(n) 级的时间复杂度, 因为所有元素只会进入栈一次, 并且出栈后再也不会进栈了.
使用单调栈解决这道题的核心思想和解法二的剪枝法有异曲同工之妙, 但要更加精巧的多, 更详细的解释可看这里.
代码如下:
- public static int largestRectangleArea(int[] heights) {
- int res = 0;
- Stack<Integer> s = new Stack<>();
- for (int i = 0; i < heights.length; ++i) {
- while (!s.isEmpty() && heights[i] < heights[s.peek()]) {
- res = Math.max(res, heights[s.pop()] * (s.isEmpty() ? i : i - s.peek() - 1));
- }
- s.push(i);
- }
- while (!s.isEmpty()) {
- res = Math.max(res, heights[s.pop()] * (s.isEmpty() ? heights.length : heights.length - s.peek() - 1));
- }
- return res;
- }
运行结果如下:
速度比前面慢的主要原因是 stack 的使用, 如果数据集能够更大一些, 才能够体现出 O(n) 解法的优势.
参考资料:
- Simple Divide and Conquer AC solution without Segment Tree
- AC clean Java solution using stack
3. [LeetCode] Largest Rectangle in Histogram 直方图中最大的矩形 https://www.cnblogs.com/grandyang/p/4322667.html
2019-05-07 于清华园
[LeetCode] 84. Largest Rectangle in Histogram
来源: http://www.bubuko.com/infodetail-3050495.html