Study Plan For Algorithms - Part43

1. 最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

class Solution:def maximalRectangle(self, matrix: List[List[str]]) -> int:if not matrix:return 0rows, cols = len(matrix), len(matrix[0])heights = [0] * colsmax_area = 0for i in range(rows):for j in range(cols):if matrix[i][j] == '1':heights[j] += 1else:heights[j] = 0stack = []for j in range(cols + 1):while stack and (j == cols or heights[stack[-1]] > heights[j]):height = heights[stack.pop()]width = j - (stack[-1] if stack else -1) - 1max_area = max(max_area, height * width)stack.append(j)return max_area

2. 分隔链表
给定一个链表的头节点 head 和一个特定值 x ，请对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。保留 两个分区中每个节点的初始相对位置。

class Solution:def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:less_head = ListNode()greater_head = ListNode()less_ptr = less_headgreater_ptr = greater_headcurr = headwhile curr:if curr.val < x:less_ptr.next = currless_ptr = less_ptr.nextelse:greater_ptr.next = currgreater_ptr = greater_ptr.nextcurr = curr.nextgreater_ptr.next = Noneless_ptr.next = greater_head.nextreturn less_head.next