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. Example:

Input: [2,1,5,6,2,3]

Output: 10

Solution 1 (Force):

func largestRectangleArea(heights []int) int {
    // find  range smallest value
    lenH := len(heights)
    maxArea := 0;
    for i := 0; i < lenH; i++ {
        area := heights[i]
        //left 
        for l := i - 1; l >= 0; l-- {
            if heights[l] >= heights[i] {
                area += heights[i]
            }else {
                break
            }
        }
        //right
        for r := i + 1; r < lenH; r++ {
            if heights[r] >= heights[i] {
                area += heights[i]
            }else {
                break
            }
        }
        if area > maxArea {
            maxArea = area
        }
        
    }
    return maxArea
}

Solution 2(stack):

//from leetcode sharing solution

type data struct {
   Height int
   Start  int
}

type stack []data

func (s stack) Peek() data {
   return s[len(s)-1]
}

func (s stack) Push(v data) stack {
   return append(s, v)
}

func (s stack) Pop() (stack, data) {
   l := len(s)
   return s[:l-1], s[l-1]
}

func (s stack) Len() int {
   return len(s)
}

func newStack(capacity int) stack {
   return stack(make([]data, 0, capacity))
}

func largestRectangleArea(heights []int) int {
   maxRectange := 0
   stack := newStack(len(heights))
   for i := 0; i <= len(heights); i++ {
      ch := 0
      start := i
      
      if i < len(heights) {
         ch = heights[i]
      }
      
      for stack.Len() > 0 {
         sd := stack.Peek()
         sh := sd.Height
         if ch < sh {
            if area := (i - sd.Start) * sh; area > maxRectange {
               maxRectange = area
            }
            stack, _ = stack.Pop()
            start = sd.Start
         } else {
            break
         }
      }
      
      stack = stack.Push(data{
         ch,
         start,
      })
   }
   
   return maxRectange
}