Problem Description:
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.
解题思路：
面积的计算肯定是长乘宽，就是index的差加一乘上最小的height。
此题O(n)的解法是维持一个递增的栈，每次出现一次递减的时候开始弹出栈中元素，维持递增性质。
最后一次的高度为0，是为了弹出所有的元素。
class Solution { public int largestRectangleArea(int[] heights) { if(heights == null) return 0; Stack<Integer> stack = new Stack<>(); int res = 0; for(int i = 0; i <= heights.length; i++) { int h = i == heights.length ? 0 : heights[i]; if(stack.isEmpty() || h >= heights[stack.peek()]) { stack.push(i); } else { int top = stack.pop(); res = Math.max(res, heights[top] * (stack.isEmpty() ? i : i - 1 - stack.peek())); i--; } } return res; } }
解法二是O(n^2)的复杂度。但是没有用到栈，提交后速度也很快，思路类似，每当出现height[i] > height[i + 1]的时候进行一次面积的计算。
class Solution { public int largestRectangleArea(int[] heights) { if(heights == null) return 0; int res = 0; for(int i = 0; i < heights.length; i++) { if(i == heights.length - 1 || heights[i] > heights[i + 1]) { int cur = heights[i]; int minH = cur; res = Math.max(res, cur); for(int j = i - 1; j >= 0; j--) { minH = Math.min(heights[j], minH); res = Math.max(res, minH * (i - j + 1)); } } } return res; } }
LeetCode 84. Largest Rectangle in Histogram
原文：https://www.cnblogs.com/rookielet/p/10517274.html