Question:
My code:
import java.util.Stack;
public class Solution {
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0)
return 0;
int count = height.length;
int[] area = new int[count + 1];
for (int i = 0; i < count; i ++)
area[i] = height[i];
area[count] = 0;
int maxArea = 0;
Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < count + 1; i++) {
if (s.isEmpty() || area[i] >= area[s.peek()])
s.push(i);
else {
while (!s.isEmpty() && area[i] < area[s.peek()]) {
int top = area[s.pop()];
int currArea = top * (s.isEmpty() ? i : i - s.peek() - 1);
if (currArea > maxArea)
maxArea = currArea;
}
s.push(i);
}
}
return maxArea;
}
public static void main(String[] args) {
int[] height = {2, 1, 5, 6, 2, 3};
Solution test = new Solution();
System.out.println(test.largestRectangleArea(height));
}
}
My test result:
这次作业是因为之前的 Max Square才找到的。因为之前看了相关的思路，所以这道题目就比较顺得写下来了。虽然最后还是出了一些小问题。
他的思路是什么呢？
其实就是将数由小到大放进栈中。当碰到一个比栈顶数（当前最大数）小的数时，将栈中比该数大的数都pop出来，算面积。然后将该数压入栈中。也就说，栈中的数一直是从小到大排列的。然后碰到小的，就将比其大的pop出来，一个个算面积，然后求出最大面积。
因为值大的不会和值小的构成矩形，只会和值大的构成矩形。所以比该数大的就全部pop出来。然后计算出来的面积是完整的。然后比该值小的数依旧存在栈里面，以后该数pop时，需要连同这些小的一起计算面积。
核心原则是：
小的不能和大的构成矩形算面积。
大的可以和小的构成矩形算面积（切掉头上方那些多余部分）。
**
总结：还是一种思路问题吧。我觉得用栈这种数据结构用的很妙。同样需要考虑的问题是，什么样的数可以进入栈。pop出栈的数据又需要满足哪些条件。
**
有点疲倦。但写着写着脑子又清醒了。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0)
return 0;
Stack<Integer> s = new Stack<Integer>();
int[] helper = new int[height.length + 1];
for (int i = 0; i < height.length; i++)
helper[i] = height[i];
int max = 0;
int zeroLocation = -1;
for (int i = 0; i < helper.length; i++) {
if (s.isEmpty() || helper[i] >= helper[s.peek()]) { // insert into stack with increasing elem values
s.push(i);
}
else {
int end = i; // get the end index
while (!s.isEmpty()) {
if (helper[s.peek()] >= helper[i]) { // if bigger, pop, area = value * (end - begin)
int index = s.pop();
int area = 0;
if (s.isEmpty()) {
int begin = zeroLocation;
area = helper[index] * (i - begin - 1);
}
else {
int begin = s.peek();
area = helper[index] * (i - begin - 1);
}
max = Math.max(max, area); // get the biggest area
}
else
break;
}
if (helper[i] > 0)
s.push(i); // push this index into stack
else
zeroLocation = i;
}
}
return max;
}
}
自己又写了一遍，终于写出来了。。花费了大约一小时，许多尝试。
最大的问题出在：
左边的边界是 s.peek() + 1;
所以我还考虑了0的情况，觉得0不该插入栈中，然后拿一个变量来记录每一个0的位置，然后算出每段的区域面积，如果栈空了，就 i - zeroLocation + 1
这个挺麻烦的。然后用我以前写的代码，网上看的，就简洁很多。0也插入进去。
如果栈空了，之前的数中一定没存在过0，否则0不会弹出。
然后，算总面积，宽为 i
如果栈不空，就拿 s.peek() + 1作为左边界，不用再去更新zeroLocation，对所有数字也是统一处理，不需要分非0或0.
简洁了很多。
这道题目是做
- Maximal Rectangle
http://www.jianshu.com/p/c86e5dec7514
想起来的。之前也做过这道题目，所以知道思路，就是把他当做等高地图那样来做。每个值表示的就是一个直方图，然后将每行的直方图作为参数送到这个函数里求出最大面积。
遍历所有行，直到找到最大值。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
Stack<Integer> s = new Stack<Integer>();
int[] h = new int[heights.length + 1];
for (int i = 0; i < heights.length; i++) {
h[i] = heights[i];
}
int max = 0;
for (int i = 0; i < h.length; i++) {
if (s.isEmpty() || h[i] >= h[s.peek()]) {
s.push(i);
}
else {
while (!s.isEmpty() && h[i] < h[s.peek()]) {
int high = h[s.pop()];
int end = i;
int begin = (s.isEmpty() ? 0 : s.peek() + 1);
int area = high * (end - begin);
max = Math.max(max, area);
}
s.push(i);
}
}
return max;
}
}
差不多的思路。一个栈。
最重要的问题是，
弹出一个值算面积，一定要首先确定他的begin and end
Anyway, Good luck, Richardo! -- 08/18/2016
My code:
public class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int[] nums = new int[heights.length + 1];
for (int i = 0; i < heights.length; i++) {
nums[i] = heights[i];
}
Stack<Integer> st = new Stack<Integer>();
int i = 0;
int max = 0;
while (i < nums.length) {
if (st.isEmpty() || nums[st.peek()] <= nums[i]) {
st.push(i);
i++;
}
else {
int index = st.pop();
int right = i - 1;
int left = st.isEmpty() ? 0 : st.peek() + 1;
int area = (right - left + 1) * nums[index];
max = Math.max(max, area);
}
}
return max;
}
}
注意找到这个直方块，比他大的最左边和最右边界限。
Anyway, Good luck, Richardo! -- 09/17/2016
