leetcode/code/lc84.java at master · mJackie/leetcode · GitHub

History

67 lines (63 loc) · 2.67 KB

Raw

package code;

import java.util.Stack;

* 84. Largest Rectangle in Histogram

* 题意：直方图中最大矩形面积

* 难度：Hard

* 分类：Array, Stack

* 思路：两种方法：1.用dp找到边界，再遍历一遍; 2.用栈，栈内存索引，保证栈内索引对应的高度是递增的，若减了即找到了右边界，出栈开始计算。因为栈内是递增的，左边界就是上个栈内的元素。若栈为空，左边界就是-1。

* Tips：和lc42做比较，都可以用栈或者dp来做. 很难，栈的操作很难想到.

* 和lc42 dp作比较和lc32栈做比较

* lc11, lc42, lc84

public class lc84 {

public static void main(String[] args) {

int[] heights = {2,1,5,6,2,3};

System.out.println(largestRectangleArea(heights));

System.out.println(largestRectangleArea2(heights));

}

public static int largestRectangleArea(int[] heights) {

Stack<Integer> st = new Stack();

int res = 0;

for (int i = 0; i <= heights.length ; i++) {

int h = (i == heights.length ? 0 : heights[i]);

if( st.size()==0 || h>heights[st.peek()] ){ //递增入栈，保证栈内索引对应的Height递增

st.push(i);

}else{

int n = st.pop(); //计算该位置height高度的矩形

int left;

if(st.isEmpty())

left = -1; //若为空，则到最左边

else

left = st.peek();

res = Math.max(res, heights[n] * (i-left-1)); //i之前的，要-1; 注意是height[n], 不是height[i]

i--; //注意i--，相当于循环出栈，总体复杂度还是O(n)，因为栈最大是heights.len

}

return res;

}

public static int largestRectangleArea2(int[] heights) {

int[] leftMax = new int[heights.length];

int[] rightMax = new int[heights.length];

for (int i = 0; i < heights.length ; i++) { //get leftMax 注意这样dp时数组中保存的边界必须是i-1或i+1，否则无法dp传递

int p = i-1;

while( p>=0 && heights[p]>=heights[i]){

p = leftMax[p];

}

leftMax[i] = p;

}

for (int i = heights.length-1; i >= 0 ; i--) { //get rightMax

rightMax[i] = i;

int p = i+1;

while( p<heights.length && heights[p]>=heights[i]){

p = rightMax[p];

}

rightMax[i] = p;

}

int res = 0;

for (int i = 0; i < heights.length ; i++) {

res = Math.max(res,(rightMax[i]-leftMax[i]-1)*heights[i]);

}

return res;

}

leetcode/code/lc84.java at master · mJackie/leetcode · GitHub

Expand file tree

Breadcrumbs

lc84.java

Latest commit

History

Breadcrumbs

lc84.java

File metadata and controls