給定 n 個(gè)非負(fù)整數(shù)舶治，用來表示柱狀圖中各個(gè)柱子的高度。每個(gè)柱子彼此相鄰车猬，且寬度為 1 霉猛。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積珠闰。
以上是柱狀圖的示例惜浅，其中每個(gè)柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]伏嗜。
圖中陰影部分為所能勾勒出的最大矩形面積坛悉，其面積為 10 個(gè)單位。
示例:
輸入: [2,1,5,6,2,3]
輸出: 10
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有承绸。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)吹散，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
算法
swift
/**
暴力解法
兩次循環(huán)八酒，查詢出所有的柱形面積空民，找到最大值
時(shí)間復(fù)雜度為O(n^2)
空間復(fù)雜度為O(1)
提交LeetCode超出時(shí)間限制
*/
func largestRectangleArea(_ heights: [Int]) -> Int {
var maxAero = 0
if heights.count < 1 {
return maxAero
}
if heights.count == 1 {
return heights[0]
}
// 左邊界
for i in 0..<heights.count {
var minHeight = heights[i]
// 右邊界
for j in i..<heights.count {
minHeight = min(minHeight, heights[j])
let max = (j-i+1) * minHeight
if max > maxAero {
maxAero = max
}
}
}
return maxAero
}
/**
暴力解法
內(nèi)循環(huán)中，找到當(dāng)前索引的左右邊界
時(shí)間復(fù)雜度為O(n^2)
空間復(fù)雜度為O(1)
提交LeetCode超出時(shí)間限制
*/
func largestRectangleArea(_ heights: [Int]) -> Int {
var maxAero = 0
if heights.count < 1 {
return maxAero
}
if heights.count == 1 {
return heights[0]
}
for i in 0..<heights.count {
var left = i
// 找出最左邊 大于等于 當(dāng)前索引的值
while left > 0 && heights[left-1] >= heights[i] {
left -= 1
}
var right = i
// 找出最右邊 大于等于 當(dāng)前索引的值
while right < heights.count-1 && heights[right+1] >= heights[i] {
right += 1
}
// 找出左右邊界最大值羞迷，計(jì)算最大面積
maxAero = max(maxAero, (right - left + 1) * heights[i])
}
return maxAero
}
/**
棧
單調(diào)棧
單調(diào)遞增棧
遍歷數(shù)組界轩，找到兩邊第一個(gè)小于它的值
當(dāng)前值 >= 棧頂元素(索引)對(duì)應(yīng)的值，入棧衔瓮，確定當(dāng)前值的右邊界
當(dāng)前值 < 棧頂元素對(duì)應(yīng)的值浊猾，出棧(確定左邊界)，直到 當(dāng)前值 >= 棧頂元素對(duì)應(yīng)的值
參考鏈接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/
時(shí)間復(fù)雜度為O(n)
空間復(fù)雜度為O(n)
*/
func largestRectangleArea(_ heights: [Int]) -> Int {
var maxAero = 0
if heights.count < 1 {
return maxAero
}
if heights.count == 1 {
return heights[0]
}
var newHeights = heights;
// 數(shù)組頭尾添加0
newHeights.append(0)
newHeights.insert(0, at: 0)
var stack = [Int]()
for i in 0..<newHeights.count {
while !stack.isEmpty && newHeights[i] < newHeights[stack.last!] {
let currentIndex = stack.popLast()!
// 左邊界
let left = stack.last! + 1
// 右邊界
let right = i - 1
maxAero = max((right - left + 1) * newHeights[currentIndex], maxAero)
}
stack.append(i)
}
return maxAero
}
來源：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/
