【代码随想录训练营】【Day 63】【单调栈-2】| Leetcode 42, 84

需强化知识点

• 单调栈强化

题目

leetcode.cn/problems/trapping-rain-water/description/" rel="nofollow">42. 接雨水

• 注意 python 数组反序用法 result [::-1]

class Solution:
    def trap(self, height: List[int]) -> int:
        # n = len(height)
        # leftMax, rightMax = [0] * n, [0] * n
        # result = 0

        # leftMax[0] = height[0]
        # for i in range(1, n):
        #     leftMax[i] = max(leftMax[i-1], height[i])
        
        # rightMax[n-1] = height[n-1]
        # for i in range(n-2, 0, -1):
        #     rightMax[i] = max(rightMax[i+1], height[i])
        
        # for i in range(1, n):
        #     sum_i = min(leftMax[i], rightMax[i])- height[i]
        #     result += sum_i
        # return result

        # 递减的，当遇到比栈顶大的，即代表遇到凹槽，弹出计算，还是存 index
        stack = [0]
        result = 0

        for i in range(1, len(height)):
            if height[i] < height[stack[-1]]:
                stack.append(i)
            elif height[i] == height[stack[-1]]:
                stack.pop()
                stack.append(i)
            else:
                while len(stack) > 0 and height[i] > height[stack[-1]]:
                    mid_height = height[stack[-1]]
                    stack.pop()
                    if stack:
                        right_height = height[i]
                        left_height = height[stack[-1]]
                        h = min(right_height, left_height) - mid_height
                        w = i - stack[-1] -1
                        result += h*w
                stack.append(i)
        return result

leetcode.cn/problems/largest-rectangle-in-histogram/description/" rel="nofollow">84. 柱状图中最大的矩形

• 双指针：记录左右侧第一个小于当前高度的下标（超时），最左侧和最右侧的处理也不同
• 单调栈：注意要在首尾加入0，0，因为不同于接雨水，可以单独成一个矩形

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # n = len(heights)
        # # 左右侧第一个小于当前高度的下标
        # left_min, right_min = [0] * n, [0] * n
        # result = 0

        # left_min[0] = -1
        # for i in range(1, n):
        #     j = i - 1
        #     while j >= 0 and heights[j] >= heights[i]:
        #         j -= 1
        #     left_min[i] = j

        # right_min[n-1] = n
        # for i in range(n-2, -1, -1):
        #     j = i + 1
        #     while j < n and heights[j] >= heights[i]:
        #         j += 1
        #     right_min[i] = j
            
        # for i in range(0, len(heights)):
        #     tmp = heights[i] * (right_min[i] - left_min[i] - 1)
        #     result = max(tmp, result)
        
        # return result

        heights.insert(0, 0)
        heights.append(0)
        n = len(heights)
        # 递增，存下标
        stack = [0]
        result = 0

        for i in range(1, n):
            if heights[i] > heights[stack[-1]]:
                stack.append(i)
            elif heights[i] == heights[stack[-1]]:   # 相同高度只需要保留更右边的
                stack.pop()
                stack.append(i)
            else:
                # 较高的柱子都要一起处理
                while stack and heights[i] < heights[stack[-1]]:
                    mid_index = stack[-1]
                    stack.pop()
                    if stack:
                        left_index = stack[-1]
                        right_index = i
                        width = right_index - left_index - 1
                        result = max(result, width*heights[mid_index])
                stack.append(i)
        return result