day_49
42. 接雨水
class Solution:def trap(self, height: List[int]) -> int:stack = []res = 0for i in range(len(height)):while(stack and height[i] > height[stack[-1]]):mid = stack.pop()if stack:h = min(height[i], height[stack[-1]]) - height[mid]w = i - stack[-1] - 1res += h * w stack.append(i)return res
84. 柱状图中最大的矩形
class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.insert(0, 0)heights.append(0)stack = []res = 0for i in range(len(heights)):while(stack and heights[i] < heights[stack[-1]]):mid = stack.pop()if stack:area = (i - stack[-1] - 1) * heights[mid]res = max(area, res)stack.append(i)return res