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.
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 =
For example,10 unit.Given height =
[2,1,5,6,2,3],return
10.
A:
--------------4 rd -------------------依然是用2个stack--------------------
代码看2nd实现。
犯的错误：
1：当要pop出indexstack之后， 要push进去的，不是当前的i，而是当前最远到达的index（因为之后的，都至少是这个height[i]的高度。
2： while的时候，没有先检查是否是stack.isEmpty()
------------------------1 st ------------------naive way--------------------
经过分析，首先的一个思路，就是，假设某个bar是最低的一个，向左右发展，得到其面积。
哎，也就是说，对for position i, treat height[i] as the ceiling, calcualte the area.
由于重复计算，代码效率不高。 代码如下
public class Solution {
public int largestRectangleArea(int[] height) {
int n = height.length;
// recording the maximum area , if we assume current position bar is the
// lowest
int[] maxAreaHere = new int[n];
int maxArea = 0;
for (int i = 0; i < n; i++) {
// we assume that current bar is the lowest
// calculate the
maxAreaHere[i] = height[i];
// calculate the adjacent left areas,
int left = i - 1;
while (left >= 0 && height[left] >= height[i]) {
maxAreaHere[i] += height[i];
left--;
}
// calculate the adjacent right areas,
int right = i + 1;
while (right < n && height[right] >= height[i]) {
maxAreaHere[i] += height[i];
right++;
}
if (maxArea < maxAreaHere[i]) {
maxArea = maxAreaHere[i];
}
}
return maxArea;
}
}
上述解法，会有TLE错误（time Limit exceed ）
原因就出在 重复计算上。
网上的解法 GeeksforGeeks Youtube. 别人的博客
思路如下：
依次加入 每个bar，加入的时候，其与之前的bar们，组成的rectangle的面积。
Solution:
Use Stack to keep track of height and start indexes
Compare current height with previous one
#1: current Larger than previous (top of height stack)
Push current height & index as candidate rectangle start position
#2: current EQUALS previous
Ignore, as largest rectangle will start from previous with same height
#3: current is less than previous
Need keep popping out previous heights, and compute the candidate rectangle with height and width (current index MINUS previous index)
Push the height and index (appropriate position) to stacks
public int largestRectangleArea(int[] height) {
Stack<Integer> stkH = new Stack<Integer>();// stack recording the height
// of bar
Stack<Integer> stkIndex = new Stack<Integer>();// stack recording
// correspnding index
int maxArea = 0;
for (int i = 0; i < height.length; i++) { // for each length
// if current bar is higher than previous, push
if (stkH.isEmpty() || stkH.peek() > height[i]) {
stkH.push(height[i]);
stkIndex.push(i);
} else if (stkH.peek() < height[i]) {
// if current bar is shorter, we need pop out those longer
// heights
// and compute the candidatesrectangle's area and update maxArea
int lastIndex = 0;// this index to keep track of the last index
// ,which wil lbe repalceing the current
// height inserting
while (!stkH.isEmpty() && stkH.peek() < height[i]) {
// we need compute the size
lastIndex = stkIndex.pop();
int tmpSize = stkH.pop() * (i - lastIndex);
if (maxArea < tmpSize)
maxArea = tmpSize;
}
// after popping those unqualifed start position, including
// current index,
// we add those back , but now, current bar is the lowest from
// lastIndex ..... i
stkH.push(height[i]);
stkIndex.push(lastIndex);
}
}
// after the process, there might still be values in stacks, pop out
// each other and test size
while (!stkH.isEmpty()) {
// we need compute the size, ( from current , down to the most left
// bar, --- height[0]
// the width = currentIndex(lat one) - height[i]
// -------- just imagining we add bar of zero at most right
int tmpSize = stkH.pop() * (height.length - stkIndex.pop());
if (maxArea < tmpSize)
maxArea = tmpSize;
}
return maxArea;
}
Mistakes:
Learned:
------------------------------------------第二遍------------------------------------
思路同上面，那个跟人学的一样
只不过，对于2个stack，我们用一个stack<int[]>代替了。int[] 的长度为2， 第一个是height[i],第二个是index， 表明了，到这个height的之前的，连贯的（大于等于该height的）最远距离。
public class Solution {
public int largestRectangleArea(int[] height) {
int maxSize = 0;
if (height.length <= 0)
return maxSize;
// assume just inserted bar is the lowest, and calculate the area
Stack<int[]> stack = new Stack<int[]>(); // int[] =={height, index}
for (int i = 0; i < height.length; i++) {
if (stack.isEmpty() || stack.peek()[0] < height[i]) {
int[] tmp = { height[i], i };
stack.push(tmp);
} else if (stack.peek()[0] > height[i]) {
int lastIndexGreaterThanCurrent = i; // greater than height[i]
while (!stack.isEmpty() && stack.peek()[0] > height[i]) {
// pop the curent stack
int[] tmp = stack.pop();
lastIndexGreaterThanCurrent = tmp[1];
int curSize = tmp[0] * (i - tmp[1] );
maxSize = Math.max(maxSize, curSize);
}
// push the current value
int[] tmp = { height[i], lastIndexGreaterThanCurrent };
stack.push(tmp);
}
}
// deal with the case that stack is not empty
while (!stack.isEmpty()) {
int[] tmp = stack.pop();
int curSize = tmp[0] * (height.length - tmp[1]);
maxSize = Math.max(maxSize, curSize);
}
return maxSize;
}
}
-------------------------第三遍-----------------------
再一次强调， 当现在的height[i]的值更小的时候， 我们要计算的，是在它之前的所有的面积， 而不是包括它的面积。！！！！！！！！！！！！！！！1
Tiger, 再仔细看看， 那几行代码吧。。。。
Mistakes:
1: 两个index相减， 其长度应该是要加1 的。 哎，丢人，这么SB的错误
2：刚开始的这个思想根本就是不对的。 当stack.peek() < height[i]的时候，我们应该计算的，是对于所有大于height[i]这个高度的 和
Learned:
No comments:
Post a Comment