One problem in No.84: largest rectangle in histogram


  • 0
    C

    The current algorithm that using stack to solve this problem seems lacking some test cases. The code below is the one passed OJ, but I do think there is a test case that this code cannot pass.

    The test case is [3,1,3,4,2,3], it is easily to see the max area is 8, which cover the last 4 histograms with height 2, but I do not think the algorithm will return the correct answer.

    Here is the code in java:
    public class Solution {

    // O(n) using one stack
    public int largestRectangleArea(int[] height) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int area = 0;
    java.util.Stack<Integer> stack = new java.util.Stack<Integer>();
    for (int i = 0; i < height.length; i++) {
    if (stack.empty() || height[stack.peek()] < height[i]) {
    stack.push(i);
    } else {
    int start = stack.pop();
    int width = stack.empty() ? i : i - stack.peek() - 1;
    area = Math.max(area, height[start] * width);
    i--;
    }
    }
    while (!stack.empty()) {
    int start = stack.pop();
    int width = stack.empty() ? height.length : height.length - stack.peek() - 1;
    area = Math.max(area, height[start] * width);
    }
    return area;
    }
    }


  • 0

    Your code returns the correct output 8 for the input [3,1,3,4,2,3].


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.