[数据结构与算法] leetcode84.柱状图中最大的矩形

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode84.柱状图中最大的矩形 -> 正文阅读

[数据结构与算法]leetcode84.柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/

思路

对heights中每个柱子，求出以当前柱子为高的最大矩形面积。

假设有以下柱状图：

在这里插入图片描述

以第1个柱子为高的最大矩形：

在这里插入图片描述

以第2个柱子为高的最大矩形：

在这里插入图片描述

以第3个柱子为高的最大矩形：

在这里插入图片描述

以第4个柱子为高的最大矩形：

在这里插入图片描述

以第5个柱子为高的最大矩形：

在这里插入图片描述

以第6个柱子为高的最大矩形：

在这里插入图片描述

设 $l e f t [i]$ 表示第 $i$ 个柱子左边第一个比它矮的柱子下标，如果不存在更矮的柱子则为 $? 1$ 。

设 $r i g h t [i]$ 表示第 $i$ 个柱子右边第一个比它矮的柱子下标，如果不存在更矮的柱子则为 $h e i g h t s . l e n g t h$

则以第 $i$ 个柱子为高的最大矩形面积为 $h e i g h t s [i] ? (r i g h t [i] ? l e f t [i] ? 1)$

只需遍历所有 $h e i g h t s [i]$ ，然后取最大值，即可得到柱状图中的最大矩形面积。

可以使用以下方法以 $O (n)$ 的时间复杂度求出 $l e f t$ 数组：

显然 $l e f t [0] = ? 1$
否则设 $j = i ? 1$ ，查看 $h e i g h t s [j]$ 的值：
1. 如果 $j = = ? 1$ 或 $h e i g h t s [j] < h e i g h t s [i]$ ，则 $l e f t [i] = j$ ，结束
2. 否则让 $j = l e f t [j]$ ，回到1

$r i g h t$ 数组的求解过程类似。

Java

class Solution {
    public int largestRectangleArea(int[] heights) {
        // left[i]表示heights[i]左边第一个小于heights[i]的元素下标
        int[] left = new int[heights.length];
        left[0] = -1;
        for (int i = 1; i < heights.length; i++) {
            int j = i - 1;
            while (j != -1 && heights[j] >= heights[i]) {
                j = left[j];
            }
            left[i] = j;
        }

        // right[i]表示heights[i]右边第一个小于heights[i]的元素下标
        int[] right = new int[heights.length];
        right[heights.length - 1] = heights.length;
        for (int i = heights.length - 2; i >= 0; i--) {
            int j = i + 1;
            while (j != heights.length && heights[j] >= heights[i]) {
                j = right[j];
            }
            right[i] = j;
        }

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
        }

        return maxArea;
    }
}

Go

func largestRectangleArea(nums []int) int {
	// leftIdx[i]表示左边第一个小于nums[i]的元素索引
	leftIdx := make([]int, len(nums))
	leftIdx[0] = -1
	for i := 1; i < len(nums); i++ {
		idx := i - 1
		for idx != -1 && nums[idx] >= nums[i] {
			idx = leftIdx[idx]
		}
		leftIdx[i] = idx
	}

    // rightIdx[i]表示右边第一个小于nums[i]的元素索引
	rightIdx := make([]int, len(nums))
	rightIdx[len(nums)-1] = len(nums)
	for i := len(nums) - 2; i >= 0; i-- {
		idx := i + 1
		for idx != len(nums) && nums[idx] >= nums[i] {
			idx = rightIdx[idx]
		}
		rightIdx[i] = idx
	}

	maxArea := 0
	for i := 0; i < len(nums); i++ {
		maxArea = int(math.Max(float64(maxArea), float64(nums[i]*(rightIdx[i]-leftIdx[i]-1))))
	}

	return maxArea
}