84.largest-rentangle-in-histogram.md

84. Largest Rectangle in Histogram

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

Brute Force

The area is width x height, there are two variables, to find the largest area, we fix the height variable and find the max of width. For the iteration, and extend width to left and right side until the height starts decreasing. It takes O(n^2).

[3, 4, 5, 7, 6, 2]

// For 7, the left wall is 3 and right is 6, so we can calculate the area.
[3 ...... 7, 6 ..]

fun largestRectangleArea(heights: IntArray): Int {
    var largest = 0
    for (i in 0 until heights.size) {
        var height = heights[i]
        var left = i - 1
        var right = i + 1
        var width = 1
        while (left >= 0 && heights[left] >= height) {
            width++
            left--
        }
        while (right < heights.size && heights[right] >= height) {
            width++
            right++
        }
        largest = max(largest, width * height)
    }
    return largest
}

private fun max(n1: Int, n2: Int) = if (n1 > n2) n1 else n2

Monotonic Stack

From brute force solution we can know the idea is to iterate every height and extend the left/right to find the max area, we will stop expending until we find the height <= current height, that is the wall so we can calculate the area.

When we're looking for the next item which is greater/less than current item, we can use monotonic stack.

fun largestRectangleArea(heights: IntArray): Int {
    var largest = 0
    // We use monotonic increasing stack, and store array index
    val stack = Stack<Int>()
    
    // We append 0 to first and last so that we can calculate for the real first and last item.
    // Adding 0 at first for [2, 1, ...] decreasing case.
    // Adding 0 at last for [..., 4, 5, 6] increasing case and the stack won't pop at all.
    var newHeights = IntArray(heights.size + 2)
    newHeights[0] = 0
    newHeights[newHeights.size - 1] = 0
    for (i in 1 until newHeights.size - 1) {
        newHeights[i] = heights[i - 1]
    }
    for (i in 0 until newHeights.size) {
        // When we find the right wall, then start to find the left wall so that we can calculate the area
        while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
            val h = newHeights[stack.pop()]
            // The height is i - 1 index, not i
            // Left wall index = stack.peek()
            val w = i - 1 - stack.peek()
            largest = max(largest, h * w)
        }
        stack.push(i)
    }
    
    return largest
}

private fun max(n1: Int, n2: Int) = if (n1 > n2) n1 else n2

References

• https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/1483815

Brute Force (My first attempt, TLE)

class Solution {
    fun largestRectangleArea(heights: IntArray): Int {
        var largest = 0
        for (i in 0 until heights.size) {
            var currentArea = heights[i]
            if (currentArea == 0) continue
            largest = max(largest, currentArea)
            var minHeight = heights[i]
            var j = i - 1
            while (j >= 0) {
                val previous = heights[j]
                if (previous == 0) break
                val width = i - j + 1
                minHeight = min(heights[j], minHeight)
                largest = max(minHeight * width, largest)
                j--
            }
        }
        return largest
    }
    
    private fun max(n1: Int, n2: Int) = if (n1 > n2) n1 else n2
    private fun min(n1: Int, n2: Int) = if (n1 < n2) n1 else n2
}