84. Largest Rectangle in Histogram
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
这是一道单调栈问题。实际上,暴力算法求解已经有一定难度了:
/** * @param {number[]} heights * @return {number} */ var largestRectangleArea = function(heights) { let max = 0 heights.forEach((h, i) => { let w = 1, l=1, r=1 while(i-l >= 0 && heights[i-l] >= h) { w++ l++ } while(i+r < heights.length && heights[i+r] >= h) { w++ r++ } max = Math.max(max, w*h) }) return max };
这个解法是优化的基础。
它的单调栈用法不太直观,在做题时很难想到。关键点仅仅在于:我们想要的是左边比自己大的数,和右边比自己大的数这一点而已。此时,问题变成了如何快速找到左右边界。
使用单调栈储存单调增序列,一旦遇到较小的数,那么比该数大的树的下标依次从栈中弹出,在弹出过程中计算面积。由于是从高到低弹出的,最低点随弹出的过程扩展,最高点则固定是遇到的较小数。
/** * @param {number[]} heights * @return {number} */ var largestRectangleArea = function(heights) { let max = 0, stack = [] heights = [0, ...heights, 0] for (let i=0; i<heights.length; i++) { if (heights[i] < heights[stack[0]]) { while(heights[stack[0]] > heights[i]) { const crt = stack.shift() max = Math.max((i - stack[0] - 1) * heights[crt], max) } } stack.unshift(i) } return max };
由于解题思路难以理解,很难说自己已经掌握了单调栈,在此记录。