ac solution code


  • 0

    Explanation:

    0_1484982417269_largestRectangleArea2-OK.jpg

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

Log in to reply
 

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