Java for LeetCode 084 Largest Rectangle in Histogram【HARD】
For example,
Given height = [2,1,5,6,2,3]
,
return 10
.
解题思路:
参考Problem H: Largest Rectangle in a Histogram 第四种思路,或者翻译版Largest Rectangle in Histogram@LeetCode,JAVA实现如下:
public int largestRectangleArea(int[] height) { Stack<Integer> stk = new Stack<Integer>(); int ret = 0; for (int i = 0; i <= height.length; i++) { int h=0; if(i<height.length) h=height[i]; if (stk.isEmpty() || h >= height[stk.peek()]) stk.push(i); else { int top = stk.pop(); ret = Math.max(ret, height[top] * (stk.empty() ? i : i - stk.peek() - 1)); i--; } } return ret; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。