柱状图中最大的矩形

2023-12-17T03:09:39.png
简单理解,对于每个高度,找到其对应的最大矩阵,然后从这些矩阵中找出最大的矩阵,则为柱状图中最大的矩阵,那给定一个高度,如何找到其对应的最大矩阵呢,即往左往右遍历,需要保证遍历的每一个高度都要大于等于该高度,直到不满足停止,这样形成的矩阵是该高度对应的最大矩阵,即:找到左边最近的小于该高度的位置 和 找到右边最近的小于该高度的位置,这需要借助单调栈(单调递减栈)
2023-12-17T03:43:00.png
以下用python代码实现:

def largestRectangleArea(heights):
    stack = []
    n = len(heights)
    right_list = [n]*n
    left_list = [0]*n
    # 找到i位置右边能延伸的最大范围
    for i in range(n):
        while len(stack) > 0 and heigths[stack[-1]] > heights[i]:
            right_list[stack[-1]] = i
            stack = stack[:-1]
        stack.append(i)
    # 找到i位置左边能延伸的最大范围
    stack = []
    i = n-1
    while i>=0:
        while len(stack) > 0 and heigths[stack[-1]] > heights[i]:
            left_list[stack[-1]] = i + 1
            stack = stack[:-1]
        stack.append(i)
    # 计算最大的矩阵
    max_value = 0
    for i in range(n):
        max_value = max(max_value,(right_list[i]-left_list[i])*heights[i])
    return max_value

这个写法还是不够好理解,尤其是在内层的while循环中,每次都增加right_list[stack[-1]] = i,变动一下当前出栈后,对应的最大值,后面再刷时去掉了这行,下面更符合理解逻辑:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        left_arr = [0]*len(heights)
        right_arr = [0]*len(heights)
        # 单调递减栈,记录左边第一个小于当前值的索引
        stack = []
        for i in range(len(heights)):
            while len(stack)>0 and heights[stack[-1]] >= heights[i]:
                stack = stack[:-1]
            left_arr[i] = (stack[-1]+1) if len(stack)>0 else 0
            stack.append(i)
        # 单调递减栈,记录右边第一个小于当前值的索引
        stack = []
        for j in range(len(heights)-1,-1,-1):
            while len(stack)>0 and heights[stack[-1]] >= heights[j]:
                stack = stack[:-1]
            right_arr[j] = (stack[-1] if len(stack)>0 else len(heights))-1
            stack.append(j)

        max_value = 0
        for i in range(len(heights)):
            cur_value = heights[i] * (right_arr[i] - left_arr[i] + 1)
            if max_value < cur_value:
                max_value = cur_value
        return max_value

上面的写法是为了更好的理解,其实也可以简化,左右范围一起算:

def largestRectangleArea(heights):
    n = len(heights)
    stack = []
    left = [0]*n
    right = [n]*n
    for i in range(n):
        while len(stack)>0 and heights[stack[-1]] > heights[i]:
            right[stack[-1]] = i
            stack = stack[:-1]
        # 当前i的最远左边是0或者单调栈中的栈顶元素对应的位置
        left[i] = stack[-1] if len(stack)>0 else -1
    max_value = max([heights[i]*(right[i]-left[i]-1) for i in range(n)])
    return max_value

接雨水

2023-12-17T03:42:01.png
对于每个位置,需要找到其左边最大值和右边最大值,然后取这两个值对应的最小值,减去该位置的高度,即为该位置能够接的水量,相对余上面一题来说更简单,下面用python实现:

def trap(height):
    left = [0]*len(height)
    right = [0]*len(height)
    cur = 0
    for i in range(len(height)):
        cur = max(cur,height[i])
        left[i] = cur
    cur = 0
    for i in range(len(height)-1,-1,-1):
        cur = max(cur,height[i])
        right[i] = cur
    s = 0
    for i in range(len(height)):
        s += min(left[i],right[i]) - height[i]
    return s