算法题--求最大矩形面积

image.png

0. 链接

题目链接

1. 题目

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

2. 思路1：尝试以每个位置作为矩形的高, 再找到宽, 然后求出最大面积

• 对于每个位置, 求出以这个位置为高的矩形中，宽度最宽的那一个矩形， 最后在所有最大矩形中，挑出最大面积
• 对于任意位置i, 以heights[i]为高的矩形，左端l和r分别为从i往左数的第一个小于heights[i]的下标，和从i往右数的第一个小于heights[i]的下标，有了这两个下标，就可以算出第i个矩形的面积了
• 所以关键问题是，对于i，如何找到l和r
• 基本想法是从i往左往右遍历寻找，这样找到所有i对应的l和r的复杂度为O(n^2)，但实际上，我们可以记录并重用每个位置i对应的l和r.
• 记录lessFromLeft[i]表示从i往左数，第1个比heights[i]小的数字所处下标, lessFromRight[i]表示从i往右数，第1个比heights[i]小的数字所处下标，则可以看到，当求lessFromLeft[8]的时候, 可以用到lessFromFromLeft[7]的值, 然后求lessFromLeft[7]的时候, 可以用到lessFromLeft[6]的值, 以此类推, 直到lessFromLeft[1], 既然有这样的依赖关系，所以我们填充lessFromLeft的值的时候, 应该优先计算lessFromLeft[1]的值，然后接着计算下标更大的值; 同理, 应该优先计算lessFromRight[n - 2]的值, 然后接着计算下标更小的值.
• 前面已经计算出了所有位置i处的l和r，那么到这里就可以计算每个位置i处作为高的矩形的面积了，然后从这些面积可以得出最大面积。

3. 代码

# coding:utf8
from typing import List


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        min_values = [[0] * n for _ in range(n)]
        dp = [[0] * n for _ in range(n)]
        max_value = 0
        for i in range(n):
            for j in range(i, n):
                if j > i:
                    min_values[i][j] = min(min_values[i][j - 1], heights[j])
                else:
                    min_values[i][i] = heights[i]
                dp[i][j] = min_values[i][j] * (j - i + 1)
                max_value = max(max_value, dp[i][j])

        return max_value


class Solution1:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        if n == 0:
            return 0

        less_from_left = [None] * n     # 每个元素往左数第一个小于该元素的位置
        less_from_right = [None] * n    # 每个元素往右数第一个小于该元素的位置
        less_from_left[0] = -1          # 特殊位置特殊处理, 方便后面计算宽度
        less_from_right[n - 1] = n      # 特殊位置特殊处理, 方便后面计算宽度

        for i in range(1, n):
            p = i - 1
            while p >= 0 and heights[p] >= heights[i]:
                p = less_from_left[p]   # 继续往左找第一个比heights[p]更小的元素
            less_from_left[i] = p       # 找到了i左边第一个比heights[i]更小的元素, 记录下来留给其他的i使用

        for i in range(n - 2, -1, -1):
            p = i + 1
            while p < n and heights[p] >= heights[i]:
                p = less_from_right[p]  # 继续往右边找第一个比heights[p]更小的元素
            less_from_right[i] = p      # 找到了i右边第一个比heights[i]更小的元素, 记录下来留给其他的i使用

        max_val = 0
        for i in range(n):
            # 计算以每个位置为高的矩形面积, 遴选出最大面积
            max_val = max(max_val, heights[i] * (less_from_right[i] - less_from_left[i] - 1))

        return max_val


def my_test(solution, heights):
    print('input: {}, output: {}'.format(heights, solution.largestRectangleArea(heights)))


solution = Solution1()
my_test(solution, [2, 1, 5, 6, 2, 3])
my_test(solution, [])

输出结果

input: [2, 1, 5, 6, 2, 3], output: 10
input: [], output: 0

4. 结果

image.png