84 Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

solution

• 单调栈: 寻找左右两边第一个比自己小的柱子。右边通过单调栈外的元素实现，左边通过单调栈里的元素实现。栈顶，栈顶的下一个元素，即将入栈的元素：这三个元素组成了最大面积的高度和宽度

  • 迭代的时候，当一个小的高度出现时，可以更新比他大的柱子和他自己构成的矩形面积了，此时把栈保存的pop出来计算

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 输入数组首尾各补上一个0
        heights = [0] + heights + [0]
        stack = [0]
        result = 0
        for i in range(1, len(heights)):
            # 单调栈: 找左右第一个比自己小的. 更新过程中，作为右边，如果比栈顶左边的元素小，则出栈计算结果
            while stack and heights[i] < heights[stack[-1]]:
                mid_height = heights[stack[-1]]
                stack.pop()
                if stack:
                    # 左边比自己小的，则是剩余栈里的栈顶
                    area = (i - stack[-1] - 1) * mid_height
                    result = max(area, result)
            stack.append(i)
        return result

时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stack = []  # 单调栈
        next_smaller_left = [0] * n
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                next_smaller_left[i] = stack[-1] + 1
            stack.append(i)
        
        stack = []
        next_smaller_right = [n - 1] * n
        for i in range(n-1, -1, -1):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                next_smaller_right[i] = stack[-1] - 1
            stack.append(i)
        
        res = heights[0]
        for i in range(n):
            height = heights[i]
            width = next_smaller_right[i] - next_smaller_left[i] + 1
            area = height * width
            res = max(res, area)
        return res

时间复杂度：O() 空间复杂度：O()

• 双指针: 找每个柱子左右两边第一个小于该柱子的柱子

follow up

42. Trapping Rain Water

1856. Maximum Subarray Min-Product