84-LargestRectangleinHistogram.go

package main

// 84. Largest Rectangle in Histogram
// Given an array of integers heights representing the histogram's bar height where the width of each bar is 1,
// return the area of the largest rectangle in the histogram.

// Example 1:
// <img src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg" />
// Input: heights = [2,1,5,6,2,3]
// Output: 10
// Explanation: The above is a histogram where width of each bar is 1.
// The largest rectangle is shown in the red area, which has an area = 10 units.

// Example 2:
// Input: heights = [2,4]
// Output: 4
 
// Constraints:
//     1 <= heights.length <= 10^5
//     0 <= heights[i] <= 10^4

import "fmt"

// stack
func largestRectangleArea(heights []int) int {
    res, n := 0, len(heights) + 2
    // Add a sentry at the beginning and the end
    getHeight := func(i int) int { if i == 0 || n-1 == i { return 0; }; return heights[i-1]; }
    max := func (x, y int) int { if x > y { return x; }; return y; }
    stack := make([]int, 0, n/2)
    for i := 0; i < n; i++ {
        for len(stack) > 0 && getHeight(stack[len(stack) - 1]) > getHeight(i) {
            // pop stack
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res = max(res, getHeight(idx)*(i- stack[len(stack) -1 ] - 1))
        }
        // push stack
        stack = append(stack, i)
    }
    return res
}

// dp
func largestRectangleArea1(heights []int) int {
    l := len(heights)
    if l == 0 {
        return 0
    }
    left, right:= make([]int, l), make([]int, l)
    for i := 1 ; i < l; i++ {
        left[i] = i
        j := i
        for left[j] - 1 >= 0 && heights[left[j] - 1] >= heights[i] {
            j = left[j] - 1
        }
        left[i] = left[j]
    }
    right[l - 1] = l - 1
    for i := l - 2; i >= 0; i-- {
        right[i] = i
        j := i
        for right[j] + 1 <= l - 1 && heights[right[j] + 1] >= heights[i] {
            j = right[j] + 1
        }
        right[i] = right[j]
    }
    res := 0
    for i := 0; i < l; i++  {
        if heights[i] * (right[i] - left[i] + 1) > res {
            res = heights[i] * (right[i] - left[i] + 1)
        }
    }
    return res
}



func main() {
    // Explanation: The above is a histogram where width of each bar is 1.
    // The largest rectangle is shown in the red area, which has an area = 10 units.
    fmt.Printf("largestRectangleArea([]int{2,1,5,6,2,3}) = %v\n",largestRectangleArea([]int{2,1,5,6,2,3})) // 10
    fmt.Printf("largestRectangleArea([]int{2,4}) = %v\n",largestRectangleArea([]int{2,4})) // 4
    fmt.Printf("largestRectangleArea([]int{2,3}) = %v\n",largestRectangleArea([]int{2,3})) // 4

    fmt.Printf("largestRectangleArea1([]int{2,1,5,6,2,3}) = %v\n",largestRectangleArea1([]int{2,1,5,6,2,3})) // 10
    fmt.Printf("largestRectangleArea1([]int{2,4}) = %v\n",largestRectangleArea1([]int{2,4})) // 4
    fmt.Printf("largestRectangleArea1([]int{2,3}) = %v\n",largestRectangleArea1([]int{2,3})) // 4
}