[LeetCode] 84. Largest Rectangle in Histogram

轉自LeetCode

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

Solution

和 42. Trapping Rain Water 相似的題目，可以用 stack 來解

但是過程中的檢查條件不一樣(參考)

在這邊的 stack 變成是一個遞增序列

當目前高度比stack的top低的時候，可以看成找到一個局部的最高

這時候開始往前找高度，並計算從該高度往右可以組成多少面積

為什麼是往右，因為 stack 是一個遞增序列，且局部最高的值會在最右邊

因此往右才可以圍出最大的面積

然後往前檢查的終止條件是，stack 的 top 必須高於目前 index 指向的高

這樣才可以保持往右和局部最高圍出面積這個條件的成立

kotlin

	class Solution {
	fun largestRectangleArea(heights: IntArray): Int {
	var ans = 0
	val stack = mutableListOf<Int>()
	var i = 0
	val finalHeights = heights + listOf(0)
	var width = 0
	var last = 0
	while(i < finalHeights.size) {
	if(stack.isEmpty() || finalHeights[stack.last()] <= finalHeights[i]) {
	stack.add(i++)
	} else {
	last = stack.last()
	stack.removeAt(stack.lastIndex)
	width = if(stack.isEmpty()) i else i - stack.last() - 1
	ans = Math.max(ans, finalHeights[last] * width)
	}
	}
	return ans
	}
	}

view raw largest_rectangle_in_histogram.kt hosted with ❤ by GitHub