首页 > 代码库 > [LeetCode]Largest Rectangle in Histogram
[LeetCode]Largest Rectangle in Histogram
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 = 10
unit.
For example,
Given height = [2,1,5,6,2,3]
,
return 10
.
public class Solution { public int largestRectangleArea(int[] height) { if(height.length == 0) return 0; Stack<Integer> stack = new Stack<Integer>(); int []arr= Arrays.copyOf(height, height.length+1); arr[height.length] = 0; int res = 0; for(int i=0;i<arr.length;){ if(stack.isEmpty()||arr[stack.peek()]<arr[i]){ stack.push(i++); }else{ int temp = arr[stack.pop()]; res = Math.max(res, temp*(stack.isEmpty()?i:i-stack.peek()-1)); } } return res; } }
[LeetCode]Largest Rectangle in Histogram
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。