# ac solution code

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.