O(n) stack based JAVA solution


  • 85
    W

    For explanation, please see http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

    public class Solution {
        public int largestRectangleArea(int[] height) {
            int len = height.length;
            Stack<Integer> s = new Stack<Integer>();
            int maxArea = 0;
            for(int i = 0; i <= len; i++){
                int h = (i == len ? 0 : height[i]);
                if(s.isEmpty() || h >= height[s.peek()]){
                    s.push(i);
                }else{
                    int tp = s.pop();
                    maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                    i--;
                }
            }
            return maxArea;
        }
    }
    

    OP's Note: Two years later I need to interview again. I came to this problem and I couldn't understand this solution. After reading the explanation through the link above, I finally figured this out again.
    Two key points that I found helpful while understanding the solution:

    1. Do push all heights including 0 height.
    2. i - 1 - s.peek() uses the starting index where height[s.peek() + 1] >= height[tp], because the index on top of the stack right now is the first index left of tp with height smaller than tp's height.

  • 0
    J
    This post is deleted!

  • 0
    J

    Nice code! but height[tp] is greater than h, right? If you want to calculate the area between two edges, you are supposed to pick the min of the two edges as the height, which is height[h], rather than height[tp]. However, the code is working in OJ. Can anybody give an explanation? thanks.


  • 0
    M

    The code compare every height[tp]'s area in stock,like, the highest bar1, the second highest2, the third highest*3....until stack is empty. then put the lower 'height[h]' into stack. Please see author's explanation.


  • 0
    J

    Thanks a lot for your reply! You can see that it took me a while to understand this:). The method is very clever, but not that straight forward to me.

    thanks,


  • 0
    R

    please explain your code, several copy paste solutions has been posted, not a single clean explanations


  • 0
    P

    The code is so nice. But it seems that OJ has added some other test cases and this solution become TLE.


  • 0

    @PhoenixWen The problem was just fixed, the code should get Accepted now.


  • 0
    W

    Can you explain code? your solution is concise, but not straightforward.


  • 0
    M

    Can someone explain why it is i - 1 - s.peek() instead of i - s.peek() ? What's the extra -1 for?


  • 6
    X

    index i and s.peek() are the right bound (exclusive) and left bound (exclusive) of the range which we use to compute the width of the rectangle, so i - s.peek() -1 is the correct value. i - s.peek() does not exclude the right bound.


  • 1
    N

    It seems faster if we do if(s.isEmpty() || h > height[s.peek()]) rather than if(s.isEmpty() || h >= height[s.peek()]). So that way we can reduce the number of calculations if there are lots of duplicates. Is it right?


  • 4
    U

    can someone tell why we need i--?


  • 10
    X

    @u.u when we in the else branch, means the h (height[i]) is smaller than height[s.peek()], what we do is updating the maxArea, but the height[i] is still waiting to be put into the stack, we do i-- to counteract the i++ statement in the for loop, so that we will get the same i in the next time.


  • 3
    O

    My notes and python implementation from the reference articles

    • For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle.
    • the key is that we are maintaing an increasing bars in the stack
    • when we meet a height, say h, that is lower than the stack's top ==> all the bars stored in the stack that has height >= h will be right bounded by h (Remember we are calculating the area with ‘x’ as the smallest bar in the rectangle.
    • At that moment, since in the stack, we are maintaining a increasing height in the stack, every time we check a bar that is right bounded by h, will also be left bounded by the height that is previous stored in the stack. So the width would go from stack[-1] + 1 to i - 1 included, which is i - stack[-1] - 1
    • If we are examing the last element in the stack, this means he is the lowest till the leftmost of the histogram, so the width would become index 0 through index i-1 included, which is i
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            heights = heights + [0]
            stack, maxArea = [], 0
            for i in range(len(heights)):
                if stack and heights[i] < heights[stack[-1]]:
                    while stack and heights[i] <= heights[stack[-1]]:
                        h = heights[stack.pop()]
                        width = i if not stack else i - stack[-1] - 1
                        maxArea = max(maxArea, h * width)
                stack.append(i)
            return maxArea
    

  • 2

    Thanks for sharing! This is really a hard problem and it takes time to understand that 2 lines at "int tp...". Let me try to explain it in my way.

    I tried going through the example [1,7,8,5,6,10,11,8]. At the end, the stack looks like [0,3,4,7], namely [1,7,8,5,6,10,11,8] -> [1,x,x,5,6,x,x,8]. Does that ring a bell with you? Wiggle subsequence!!! h[0] < (h[1] < h[2]) > h[3] < h[4] < (h[5] < h[6]) > h[7]. It means that 1) the height in the "gaps" must be taller than left and right. Meanwhile, 2) the height on stack itself is increasing subsequence.

    These two facts are the reason why it's safe to calculate area by height[j] * (i - 1 - s.peek()) where left=s.peek() and right=i-1, since height of all rectangles between left and right must be >= height[j].


  • 10
    N

    The best explanation I have seen so far: https://www.youtube.com/watch?v=VNbkzsnllsU


  • 0
    S

    @namxh that's indeed the best explanation


  • 0
    L

    The explanation is also helpful:)
    https://www.youtube.com/watch?v=ZmnqCZp9bBs


  • 0
    F

    @u.u
    it should goes like this, much easier to understand
    while (i <= len) {
    int h = (i == len ? 0 : heights[i]);
    if (s.isEmpty() || h >= heights[s.peek()]) {
    s.push(i);
    i++;
    } else {
    int tp = s.pop();
    int area = heights[tp] * (s.isEmpty() ? i : i - 1 - s.peek());
    maxArea = Math.max(maxArea, area);
    }
    }


Log in to reply
 

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