LeetCode : 84. Largest Rectangle in Histogram

[congr]

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

[congr]

The level of this question is "Hard", but brute force is accepted.

class Solution {
    public int largestRectangleArea(int[] heights) {
        int largest = 0, N = heights.length;
        
        for (int i = 0; i < N; i++) {
            int min = Integer.MAX_VALUE;
            for (int k = i; k < N; k++) {
                min = Math.min(min, heights[k]);
                largest = Math.max(largest, min * (k-i+1));
            }
        }
      
        return largest;
    }
}

0 ~ 0
0 ~ 1
0 ~ 2
0 ~ 3
..
1 ~ 1
1 ~ 2
1 ~ 3
…
2 ~ 2
2 ~ 3
..
3 ~ 3
3 ~ 4
3 ~ 5
..
4 ~ 4
4 ~ 5
..
5 ~ 5

[congr]

[congr]

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