0084. Largest Rectangle in Histogram

84. Largest Rectangle in Histogram #

题目 #

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.

Example:


Input: [2,1,5,6,2,3]
Output: 10

题目大意 #

给出每个直方图的高度,要求在这些直方图之中找到面积最大的矩形,输出矩形的面积。

解题思路 #

用单调栈依次保存直方图的高度下标,一旦出现高度比栈顶元素小的情况就取出栈顶元素,单独计算一下这个栈顶元素的矩形的高度。然后停在这里(外层循环中的 i–,再 ++,就相当于停在这里了),继续取出当前最大栈顶的前一个元素,即连续弹出 2 个最大的,以稍小的一个作为矩形的边,宽就是 2 计算面积…………如果停在这里的下标代表的高度一直比栈里面的元素小,就一直弹出,取出最后一个比当前下标大的高度作为矩形的边。宽就是最后一个比当前下标大的高度和当前下标 i 的差值。计算出面积以后不断的更新 maxArea 即可。

代码 #


package leetcode

import "fmt"

func largestRectangleArea(heights []int) int {
	maxArea, stack, height := 0, []int{}, 0
	for i := 0; i <= len(heights); i++ {
		if i == len(heights) {
			height = 0
		} else {
			height = heights[i]
		}
		if len(stack) == 0 || height >= heights[stack[len(stack)-1]] {
			stack = append(stack, i)
		} else {
			tmp := stack[len(stack)-1]
			fmt.Printf("1. tmp = %v stack = %v\n", tmp, stack)
			stack = stack[:len(stack)-1]
			length := 0
			if len(stack) == 0 {
				length = i
			} else {
				length = i - 1 - stack[len(stack)-1]
				fmt.Printf("2. length = %v stack = %v i = %v\n", length, stack, i)
			}
			maxArea = max(maxArea, heights[tmp]*length)
			fmt.Printf("3. maxArea = %v heights[tmp]*length = %v\n", maxArea, heights[tmp]*length)
			i--
		}
	}
	return maxArea
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者