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

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

需强化知识点

• 单调栈强化

题目

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# 递减的，当遇到比栈顶大的，即代表遇到凹槽，弹出计算，还是存 indexstack = [0]result = 0for 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_heightw = i - stack[-1] -1result += h*wstack.append(i)return result

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 resultheights.insert(0, 0)heights.append(0)n = len(heights)# 递增，存下标stack = [0]result = 0for 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 = iwidth = right_index - left_index - 1result = max(result, width*heights[mid_index])stack.append(i)return result