Largest Rectangle in Histogram
Givennnon-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.
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area =10
unit.
For example,
Given height =[2,1,5,6,2,3]
,
return10
.
属于思想很难,但是程序很简单的题目。
有几个心得:
1 也曾经考虑过需要记录第一最低高度,第二最低高度,第三最低高度,怎么就是没有想出来是需要使用栈来保持这样的数据呢?
答:下次遇到类似的题目要记住,需要使用栈来保存数据。
2 当前柱子,怎么才算是组成了最大直方图面积呢?
答:每个方柱计算只需要计算自己的最大直方图就可以了,不需要考虑比自己低的方柱,因为比自己低的方柱是由比自己低的方柱负责的!
本题的精要思想:每个方柱都只需要和自己邻近的大于自己的方柱组成本方柱最大直方图,然后所有,n个,直方图比较,最大的直方图就是答案了。
我看了两个小时,楞是没想到解决方法。想出了个二分法,不过时间效率是O(nlgn),最坏情况还是O(n*n),所以超时。
没看过类似题目,真觉得是耳目一新的题目,不过这道题的最优解,O(n)时间复杂度,要自己研究出来,我估计起码是半个天才了。
思考这道题的时候总觉得差那么一点点,一点点就能写出O(n)算法来了,不过就是差那么一点点,那么一点点原来是如此难以逾越的。
警惕自己,也警惕后来人,不要以为“差不多”啊!那一步之遥,中间隔的也许是万丈深渊啊。
参考了一下leetcode上的程序,自己写了个:
int largestRectangleArea(vector<int> &h)
{
h.push_back(0);
int n = h.size();
//初始化应该是0,不应该是INT_MIN
int maxArea = 0;
stack<int> stk;
for (int i = 0; i < n; )
{
//注意别漏了stk.empty()这个条件
//且条件不是h[i]<=h[i+1],是入栈的的栈顶元素和当前元素对比
if (stk.empty() || h[stk.top()]<=h[i]) stk.push(i++);
else
{
int t = stk.top();
stk.pop();
maxArea = max(maxArea, h[t]*(stk.empty()? i:i-1-stk.top()));
}
}
return maxArea;
}
精典程序,让人叹服,感觉每句,每个细节都优化到极点了,不能修改了。
//2014-2-13 update
int largestRectangleArea(vector<int> &h)
{
stack<int> stk;
h.push_back(INT_MIN);
int max_are = 0;
for (int i = 0; i < h.size(); )
{
if (stk.empty() || h[i] >=h[stk.top()]) stk.push(i++);
else
{
int height = stk.top();
stk.pop();
int width = stk.empty()? i : i - stk.top() - 1;
max_are = max(max_are, width * h[height]);
}
}
return max_are;
}
分享到:
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
1. Introduction ... Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
leetcode 答案解析 golang解答
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
703.Kth_Largest_Element_in_a_Stream数据流中的第K大元素【LeetCode单题讲解系列】
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
100个leetCode详细解答
leetcode中文版
Leetcode Solutions in Rust, Advent of Code Solutions in Ru
这个方法实现的程序通过了LeetCode检测,提示用了16个测试,用时492ms,超过了75%的人
vs code LeetCode 插件
来源:力扣(LeetCode) 链接::过滤特殊情况,
上面是一个直方图,其中每个条的宽度为 1,给定高度 = [2,1,5,6,2,3]。 最大的矩形显示在阴影区域中,其面积 = 10 单位。 实现 1:O(n^2) class Solution { public int largestRectangleArea ( int [] heights )...
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
LeetCode-Swift, 快速LeetCode解决方案 LeetCodeLeetCode在线判断是一个包含很多收费算法的网站。 them Google Google Google Google LinkedIn this this repo 。 请免费参考并收费STAR以支持这个 repo,
LeetCode 刷题汇总1