largest_rectangle_in_histogram

  • 2022-12-14
  • 浏览 (519)

largest_rectangle_in_histogram.go 源码

package main

import (
	"math"
)

// 柱状图中最大的矩形

// 暴力法,执行会超时
func largestRectangleArea1(heights []int) int {
	if len(heights) == 1 {
		return heights[0]
	}
	max := 0
	for i := 0; i < len(heights); i++ {
		min := heights[i]
		for j := i; j < len(heights); j++ {
			if heights[j] < min {
				min = heights[j]
			}
			max = int(math.Max(float64(max), float64(min*(j-i+1))))
		}
	}
	return max
}

// 优化的暴力
func largestRectangleArea2(heights []int) int {
	if heights == nil || len(heights) == 0 {
		return 0
	}

	res := 0
	for i := 0; i < len(heights); i++ {
		left, right := i, i

		for left > 0 && heights[left-1] >= heights[i] {
			left--
		}
		for right < len(heights)-1 && heights[right+1] >= heights[i] {
			right++
		}

		res = int(math.Max(float64(res), float64(heights[i]*(right-left+1))))
	}
	return res
}

// 使用一个栈
func largestRectangleArea3(heights []int) int {
	stack, res := []int{-1}, 0
	for i, v := range heights {
		for len(stack) > 1 && heights[stack[len(stack)-1]] > v {
			n := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res = int(math.Max(float64(res), float64(heights[n]*(i-stack[len(stack)-1]-1))))
		}
		stack = append(stack, i)
	}

	if len(stack) > 1 {
		k := stack[len(stack)-1]
		for len(stack) > 1 {
			n := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res = int(math.Max(float64(res), float64(heights[n]*(k-stack[len(stack)-1]))))
		}
	}
	return res
}

你可能感兴趣的文章

min_stack

next_greater_element_i

queue_using_stack

0  赞