[leetcode] Largest Rectangle in Histogram

这题做了好几遍都是每次做要想很久甚至要搜索..
这里纪录下来 印象深刻点

重点是用一个base on nums[index]递增的stack.. 来记录index...
一旦遇到比stack top小的 pop out.. 接着用当前i减去stack top之前的数再减1来计算宽度 (因为stack top之前的index代表着第一个比stack top小的高，这样求宽度就对了）

edge case 在最后加一个0来trigger 最后的结果计算
参考这个网址里的图：http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
文章写得太繁琐了不过。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public class Solution { public int largestRectangleArea(int[] height) { if (height == null || height.length == 0) return 0; Stack<Integer> stack = new Stack<Integer>(); int h2[] = Arrays.copyOf(height, height.length+1); int maxArea = 0; for (int i = 0; i < h2.length; i++){ while (!stack.isEmpty() && h2[stack.peek()] > h2[i]){ int index = stack.pop(); int width = i - (stack.isEmpty()?0:(stack.peek())+1); maxArea = Math.max(maxArea, h2[index]*width); } stack.push(i); } return maxArea; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class Solution { public int largestRectangleArea(int[] height) { if (height == null || height.length == 0){ return 0; } int i = 0; int maxArea = 0; Stack<Integer> stack = new Stack<Integer>(); int[] copyHeight = Arrays.copyOf(height, height.length+1); while(i < copyHeight.length){ if (stack.isEmpty() || copyHeight[i] >= copyHeight[stack.peek()]){ stack.push(i++); }else{ maxArea = Math.max(maxArea, copyHeight[stack.pop()]*(stack.isEmpty()?i:i-stack.peek()-1)); if (stack.isEmpty()&&i!=height.length){ stack.push(i); } } } return maxArea; } }