# 84 Largest Rectangle in Histogram

將histogram用一個array表示，找出該histogram中最大的長方形面積。

idea:

  從histogram底端往上掃描，

  h=1~最高值

      計算該h可以有的最大面積\(最多連續幾個bar都有超過h\)

      更新max

  return max

pseudocode:

h = 1;  
maxRec = minvalue  
int maxWidth = 0;  
int width = 0;  
int less = 0;  
maxRec = minvalue  
while(h < max in heights)
  for each element in heights
  if(heights[i] > h)
    width++;
  else
    update maxWidth
    width = 0
    less++;

  if(less == heights.length)
    break;

  calculate rec and update maxRec

return maxRec

Code(TLE)

if(heights.length == 0)
    return 0;
if(heights.length == 1)
    return heights[0];

int h = 0;
int maxRec = Integer.MIN_VALUE;
for(int j=0; j<heights.length; j++){
    int maxWidth = 0;
    int width = 0;
    int less = 0;
    h = heights[j];

    for(int i=0; i<heights.length; i++){        
        if(heights[i] >= h){
            //System.out.print(heights[i] + " ");
            width++;
        }
        else{
            maxWidth = width > maxWidth ? width : maxWidth;
            width = 0;
            less++;
        }
    }

    //System.out.println();
    maxWidth = width > maxWidth ? width : maxWidth;

    if(less == heights.length)
        break;

    //System.out.println(h + " " + maxWidth);
    int rec = h * maxWidth;
    maxRec = rec > maxRec ? rec : maxRec;
    //h++;
}

return maxRec;

這個解法是O(n^2)，會time limit exceed! 照input形式來看，應該可以降到O(n)，也就是把所有input讀完的同時就得到答案。

idea 2: 用stack來存走過的bar的index，當遇到bar比stack.peek()還要矮時，就把bar裡比較高的都清掉，清的同時算出該bar高度的最大面積。

pseudocode:

stack to save index of each bar
maxRec
go through each bar in histogram,
    while current bar is shorter than top bar
    bar = pop out top bar in stack,
    calculate the rec this bar can have
    update maxRec
push current bar to stack

if stack is not empty,
    clean stack and calculate rec for each bar

Code:

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxRec = 0;
        stack.push(-1);
        int i;
        for(i=0; i<heights.length; i++){
            while(stack.peek()!=-1 && heights[stack.peek()] > heights[i]){
                int curIdx = stack.pop();
                int rec = heights[curIdx] * (i-stack.peek()-1);
                maxRec = Math.max(rec,maxRec);
            }
            stack.push(i);
        }

        while(stack.peek() != -1){
            int curIdx = stack.pop();
            int rec = heights[curIdx] * (i-stack.peek()-1);
            maxRec = Math.max(rec,maxRec);
        }

        return maxRec;
    }
}

# 84

# 84 Largest Rectangle in Histogram

results matching ""

No results matching ""