**Explanation:**

*This solution is based on Stack:*

```
1. maxWidth[x] = rightBound - leftBound:
1) leftBound : (the first left index lower than height[x] + 1) or histogram's start bound
2) rightBound : the first right index lower than height[x] or histogram's end bound
(height of end bound of is -1, is always rightBound of its left neighbor)
2. Rectangle[x] : rectangle of x = maxWidth[x] * height[x] = (rightBound - leftBound) * height[x]
3. Return: max of Rectangle[x] in 0...n-1
```

**Swift Code**

```
/*
Solution1. Stack. time = O(n); space = O(n)
*/
func largestRectangleArea(_ heights: [Int]) -> Int {
let stack = Stack<Int>()
var i = 0
var largestRectangle = 0
while i <= heights.count {
let heightI = (i != heights.count) ? heights[i] : -1// -1: Dummy height of the last item
if stack.isEmpty() || heightI >= heights[stack.peek()!] {
// push highest index
// max of largestRectangle[x]: only calculate when reach rightBound, which is on the downside wave
stack.push(i)
i += 1
} else {// i is rightBound of x: first right index lower than heights[x] (x=stack.peek() : the last highest item)
// stack:
//
// | x | <-- top
// | x's leftBound | <-- first left index lower than hights[x]
let x = stack.pop()!
let rightBound = i
// leftBound : the first left index lower than height[x] + 1
let leftBound = stack.isEmpty() ? 0 : (stack.peek()! + 1)
let maxWidthX = rightBound - leftBound
let rectangleX = heights[x] * maxWidthX
largestRectangle = max(largestRectangle, rectangleX)
}
}
return largestRectangle
}
public class Stack<T> {
public var items = [T]()
public func push(_ item: T) {
items.append(item)
}
public func pop() -> T? {
return items.removeLast()
}
public func peek() -> T? {
return items.last
}
public func isEmpty() -> Bool {
return (items.count == 0)
}
}
```