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
}``````