Problem Statement
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.
For example,
Given height =
[2,1,5,6,2,3],
return
10.
Original LeetCode problem page
My Solution in Swift
I used a stack to make the solution run in linear time O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
func largestRectangleArea(heights: [Int]) -> Int { var widths = [Int](count: heights.count, repeatedValue: 1) var stack: [Int] = [] var largestRectangleArea = 0 // calc left half of width for each reference histogram bar for var i = 0; i < heights.count; ++i { while let sIdx = stack.last { if heights[sIdx] < heights[i] { break } stack.removeLast() } if let sIdx = stack.last { widths[i] += i - sIdx - 1 } else { widths[i] += i } stack.append(i) } stack.removeAll(keepCapacity: true) // calc right half of width for each reference histogram bar while find out // the largest rectangle for var i = heights.count - 1; i >= 0; --i { while let sIdx = stack.last { if heights[sIdx] < heights[i] { break } stack.removeLast() } if let sIdx = stack.last { widths[i] += sIdx - i - 1 } else { widths[i] += heights.count - 1 - i } stack.append(i) largestRectangleArea = max(widths[i] * heights[i], largestRectangleArea) } return largestRectangleArea } |
Try It Yourself
1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:
$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution
The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)
| Problem1 | Time2 | Test Cases3 | My Xcode Project4 |
| Largest Rectangle in Histogram | 6.869ms |