Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/84.html

84	Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1,
find the area of largest rectangle in the histogram.


Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

@tag-stack

Algorithm

keyword: “Eliminate the shadow”, that is, the lowest bar is the length of a side

Intuitively, the area of ​​the two bars depends on the shortest and lowest bar among them.

My own doubt is if it is [1,2,3,4,1,2,3,4].

How to prove that the first 1 and last 4 restricted rectangles will definitely not be the largest? Because the stack only maintains the current one, note that there is only one, an increasing sequence.

Simplified to [1,2,1,2], then the maximum area is the area 4 formed by the first 1 and the last 2

  • So the key is that the push and pop conditions of the stack must ensure that the lowest bar is always in the stack.

Extend to eg. [3,1,2,1,2], the largest area also comes from the area formed by the first and last bar at 5.

Because the lowest one will always be in the stack, and the stack will eventually pop to empty, The last pop is the smallest bar. At this time, the shortest bar is multiplied by the length from the first to the last.

The whole question will be clear if you understand this: int currentWidth = sk.isEmpty()? i: (i-1-sk.peek());

sk.peek() is definitely the essence of the quintessence, to find the width of the largest rectangle, I wrote i-currentIndex at the beginning, but I ignored the situation when counting 4 in 2, 8, 8, 4, 6, 8. There are two 88 in front of 4, that is, the width should be from the first 8 to the last 8. At this time, to find this width, you need sk.peek() to find the previous small index

There is another pit, which is the application of dummy end, which has the same effect as dummy head, allowing the for loop to start and run normally.

Arrays.copyOfRange(origin, start, end), if end exceeds the length of the origin array, 0 will be added automatically

The best test case:

  • 2,1,2
  • 2,0,2
  • 2,0,2,1,2

Code

Java

  • import java.util.Arrays;
import java.util.Stack;

public class Largest_Rectangle_in_Histogram {

    public int largestRectangleArea(int[] rowarray) {

        // stack is to push array index of each element
        Stack<Integer> sk = new Stack<Integer>();

        // length+1, in the end add a dummy element as 0
        int[] row = new int[rowarray.length + 1];
        // @note: Arrays.copyOf()
        row = Arrays.copyOf(rowarray, rowarray.length + 1);

        int max = 0;

        // for (int i = 0; i < row.length; i++) {
        int i = 0;
        while (i < row.length) {

            // @note: careful about duplicate numbers being pushed
            //          "<=" and "<" both AC, since same height bar will be popped and checked anyway, just a matter of when popped
            // if (sk.isEmpty() || row[sk.peek()] <= row[i]) { @note: this is AC also
            if (sk.isEmpty() || row[sk.peek()] < row[i]) {
                sk.push(i);
                i++;
            } else { // value of index-i is smaller than current stack top

                // @note:  to get lowest bar, since other bars are all larger than it
                int currentLowestBarIndex = sk.pop();
                int edge1 = row[currentLowestBarIndex];
                // @note: empty meaning just popped lowest bar
                // @note: sk.peek() is
                int edge2 = sk.isEmpty() ? i : (i - 1 - sk.peek()); // i-1-peek is ok, since it's monotonic increasing stack

                // calculate area
                max = Math.max(max, edge1 * edge2);
            }
        }

        return max;
    }

}

  • // OJ: https://leetcode.com/problems/largest-rectangle-in-histogram/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)
class Solution {
public:
    int largestRectangleArea(vector<int>& A) {
        int N = A.size(), ans = 0;
        vector<int> prevSmaller(N, -1), nextSmaller(N, N);
        for (int i = N - 2; i >= 0; --i) {
            int j = i + 1;
            while (j < N && A[j] >= A[i]) j = nextSmaller[j];
            nextSmaller[i] = j;
        }
        for (int i = 1; i < N; ++i) {
            int j = i - 1;
            while (j >= 0 && A[j] >= A[i]) j = prevSmaller[j];
            prevSmaller[i] = j;
        }
        for (int i = 0; i < N; ++i) ans = max(ans, (nextSmaller[i] - prevSmaller[i] - 1) * A[i]);
        return ans;
    }
};

  • class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stk = []
        left = [-1] * n
        right = [n] * n
        for i, h in enumerate(heights):
            while stk and heights[stk[-1]] >= h:
                right[stk[-1]] = i
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))

############

class Solution(object):
  def largestRectangleArea(self, height):
    """
    :type height: List[int]
    :rtype: int
    """
    if not height:
      return 0
    height.append(-1)
    stack = []
    ans = 0
    for i in range(0, len(height)):
      while stack and height[i] < height[stack[-1]]:
        h = height[stack.pop()]
        w = i - stack[-1] - 1 if stack else i
        ans = max(ans, h * w)
      stack.append(i)
    height.pop() # restore, pop -1 
    return ans

All Problems

All Solutions