leetcode84.柱状图中最大的矩形

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

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

假设有以下柱状图：

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

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

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

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

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

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

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

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

则以第 i i i个柱子为高的最大矩形面积为 h e i g h t s [ i ] ∗ ( r i g h t [ i ] − l e f t [ i ] − 1 ) heights[i]*(right[i] - left[i] - 1) heights[i]∗(right[i]−left[i]−1)

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

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

• 显然 l e f t [ 0 ] = − 1 left[0] = -1 left[0]=−1
• 否则设 j = i − 1 j=i-1 j=i−1，查看 h e i g h t s [ j ] heights[j] heights[j]的值：
  1. 如果 j = = − 1 j==-1 j==−1或 h e i g h t s [ j ] < h e i g h t s [ i ] heights[j]
  2. 否则让 j = l e f t [ j ] j=left[j] j=left[j]，回到1

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

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;
    }
}

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
}