Leetcode 刷题笔记1 单调栈part02

leetcode 42 接雨水

本题用双指针法更为浅显易懂

双指针法：

class Solution:def trap(self, height: List[int]) -> int:leftheight, rightheight = [0] * len(height), [0] * len(height)ans = 0leftheight[0] = height[0]for i in range(1, len(height)):leftheight[i] = max(height[i], leftheight[i - 1])rightheight[-1] = height[-1]for i in range(len(height) - 2, -1, -1):rightheight[i] = max(height[i], rightheight[i + 1])for i in range(len(height)):total = min(leftheight[i], rightheight[i]) - height[i]ans += totalreturn ans

单调栈：

class Solution:def trap(self, height: List[int]) -> int:stack = [0]ans = 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 stack 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] - 1ans += h * wstack.append(i)return ans

leetcode 84 柱状图的最大的矩形

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.insert(0, 0)heights.append(0)stack = [0]ans = 0for 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_heightans = max(area, ans)stack.append(i)return ans

双指针法：
 

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:n = len(heights)min_left_index = [0] * nmin_right_index = [0] * nmin_left_index[0] = -1result = 0for i in range(1, n):temp = i - 1while temp >= 0 and heights[temp] >= heights[i]:temp = min_left_index[temp]min_left_index[i] = tempmin_right_index[n - 1] = nfor i in range(n - 2, -1, -1):temp = i + 1while temp < n and heights[temp] >= heights[i]:temp = min_right_index[temp]min_right_index[i] = tempfor i in range(len(heights)):area = heights[i] * (min_right_index[i] - min_left_index[i] -1)result = max(result, area)return result