算法题记录 1

83.删除排序链表中的重复元素（简单）

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。即链表去重。

涉及知识点

链表处理

解决思路

该题的解决思路非常简单，常规操作，先判断处理各种特殊情况。如先判断链表是否为空。

接着我们从头节点开始以次获取链表中每个节点信息，当我们获取节点a的信息时，因为链表有序，直接把a节点的下一个节点拿来与该节点进行大小比较。如果值相等，那么我们将a的next指针指向下下个节点，跳过有重复元素的节点，如果不同，就获取下一节点信息重复上述操作。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        cur=head
        while cur.next:
            if cur.next.val==cur.val:
                cur.next=cur.next.next
            else:
                cur=cur.next
        return head

82.删除排序链表中的重复元素2（中等）

在上一题的基础上要求删除重复的所有节点，比如有多个3，那么值为3的节点都应被删去。

涉及知识点

链表处理

解决思路

因为要删去所有值相同的节点，我们上一题的思路就需要稍作改变。在上一题中我们站在值为3的节点上删去后续也为3的节点，但这题要求我们所站的3也被删除，意味着我们需要把一次性访问的节点的数量变大，如1->2->3->3->4这一链表，我们需要站在2处访问next和next的next，当存在时，记录next的值，判断next的next的值是否与该值相等，如若相等，那么next与next的next都应被删除（while反复判断完成），我们2的next应指向4。所以整体思路变为，确认next和next的next存在，并判断删除。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur=dummy=ListNode(next=head)
        while cur.next and cur.next.next:
            val=cur.next.val
            if cur.next.next.val==val:
                while cur.next and cur.next.val==val:
                     cur.next=cur.next.next
            else:
                cur=cur.next
        return dummy.next

84.柱状图中的最大矩形（困难）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

涉及知识点

单调栈

解决思路

假设我们有2、1、5、6、2、3这样的柱状图，对于5而言，他能作为“高”直接参与形成的矩形仅有5、6的组合，受限于左右两边小于5的1和2。这时思路就很明显了，找到第k个柱形受限于的两边的小于它的柱形i、j，j-i-1就是k作为“高”参与形成的矩形的“宽”。只需遍历每个柱形通过max（）找出最大值即可。问题简单化为如何找到每个柱形受限于的两边的柱形。我们创建两个列表left和right来对每个柱形左边和右边的第一个小于它的柱形序号进行存储。如left[2]=1，right[2]=4。问题来到left和right如何生成。这里采用单调栈的思路，创建一个栈st，该栈保存的序号柱形的值都是递增的，当创建left[1]时，我们栈里有0，序号0对应的值为2，而将入栈的1小于等于2，那就将2弹出，直到栈顶的序号所指的柱形的值小于1或栈为空，循环过后如果栈中还有元素，我们保存该序号作为left[1]，并将1加入栈中，否则代表1左边的柱形都能参与生成矩形，left[1]记为-1。反复上述操作，我们得到了left。right的获取方式同上，不过是采取反向遍历range(n-1,-1,-1)。

这里采用单调栈的直觉来源于，如果左边的柱形小于当前柱形，那么肯定不能参与矩形的生成，left[i]=i-1，而如果左边的柱形大于等于当前柱形，我们就需要反复弹出左边的柱形，找到小于当前柱形的序号，作为left[i]，事实上在这样的过程中如果我们多次遇到当前柱形大于左边柱形的情况，栈的元素越来越多，并且是单调栈。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n=len(heights)
        left=[-1]*n
        st=[]
        for i,x in enumerate(heights):
            while st and x<=heights[st[-1]]:
                st.pop()
            if st:
                left[i]=st[-1]
            st.append(i)
        
        right=[n]*n
        st.clear()

        for i in range(n-1,-1,-1):
            x=heights[i]
            while st and x<=heights[st[-1]]:
                st.pop()
            if st:
                right[i]=st[-1]
            st.append(i)
        
        ans=0
        for h,l,r in zip(heights,left,right):
            ans=max(ans,h*(r-l-1))
        return ans

85.最大矩形（困难）

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

涉及知识点

前缀和、单调栈

解决思路

该题同上一题也是计算最大面积，计算最大面积的思路也应采用单调栈，不同的是单调栈中序号所指的值应该是什么？我们回顾涉及表格的算法题，如动态规划的表格。处理表格时为了规律整洁，我们往往采取从上到下，从左到右的顺序遍历每种情况。在该题中我们同样能这样做。引入前缀和的思想，我们有mxn的矩阵，让pre[]列表保存该行往上每列连续1的最大长度。比如第一列为1，1，1，0，当我们讨论到第三行时，pre[0]就该为3，而pre[]就作为上题中的柱形大小进行最大面积计算。从第一行开始对每一行进行这样的计算直到最后一行后，我们就知道了整个矩形表格能构成的最大矩形面积是多少。也就是说，总思路为：1.对每行遍历 2.在每行的基础上创建pre[]前缀和 3.利用pre[]进行单调栈面积计算，通过max（）保留最大值 4.重复1步骤，对下一行进行同样操作。

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        m,n=len(matrix),len(matrix[0])
        pre=[0]*(n+1)
        res=0

        for i in range(m):
            for j in range(n):
                pre[j]=pre[j]+1 if matrix[i][j]=='1' else 0
            
            stack=[-1]
            for k,num in enumerate(pre):
                while stack and pre[stack[-1]]>num:
                    index=stack.pop()
                    res=max(res,(k-stack[-1]-1)*pre[index])
                stack.append(k)

        return res

86.分隔链表（中等）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

涉及知识点

链表操作

解决思路

解决思路非常简单，拿到x值，创建两个新链表，遍历原链表中每个节点的值，如果节点值小于x，就进入small链表，大于x就进入big链表，最后将small链表与big链表拼接即可。

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        sml_dummy,big_dummy=ListNode(0),ListNode(0)
        sml,big=sml_dummy,big_dummy
        while head:
            if head.val<x:
                sml.next=head
                sml=sml.next
            else:
                big.next=head
                big=big.next
            head=head.next
        sml.next=big_dummy.next
        big.next=None
        return sml_dummy.next