Python小白 Leetcode刷题历程 No.81-No.85 搜索旋转排序数组Ⅱ、删除排序链表中的重复元素Ⅱ、删除排序链表中的重复元素、柱状图中最大的矩形、最大矩形
写在前面：
作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。
有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。
觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：
1.题目，难度
2.题干,题目描述
3.题解代码（Python3（不是Python，是Python3））
4.或许有用的知识点（不一定有）
5.解题思路
6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）
········································································································································································
No.81.搜索旋转排序数组Ⅱ
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def search(self, nums: List[int], target: int) -> bool:
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
if nums[mid] == nums[left] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid -1
else:
left = mid +1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid -1
return False
或许有用的知识点：
这道题要用到二分算法。
二分算法的mid值用‘mid = left + (right - left) // 2’比较好，这样可以最大限度的防止溢出。
解题思路：
二分法，判断二分点，有几种可能性：
1.直接 nums[mid] == target
2.当数组为 [1,2,1,1,1],nums[mid] == nums[left] == nums[right]，需要 left++, right --;
3.当 nums[left]<= nums[mid]，说明是在左半边的递增区域
a. nums[left] <=target < nums[mid]，说明 target 在 left 和 mid 之间。我们令 right = mid - 1;
b. 不在之间，我们令 left = mid + 1;
4.当 nums[mid] < nums[right]，说明是在右半边的递增区域
a. nums[mid] < target <= nums[right]，说明 target 在 mid 和 right 之间，我们令 left = mid + 1
b. 不在之间，我们令 right = mid - 1;
时间复杂度：O(logn)。
No.82.删除排序链表中的重复元素Ⅱ
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
dummy = ListNode(-999)
dummy.next = head
slow = dummy
fast =dummy.next
while fast:
while fast.next and slow.next.val == fast.next.val:
fast = fast.next
if slow.next == fast:
slow = fast
else:
slow.next = fast.next
fast = fast.next
return dummy.next
或许有用的知识点：
当处理链表且需要考虑空链表时，我们或许可以设置一个哑结点，即dummy=LIstNode（-999），dummy.next = head。
这道题可以用快慢指针的思想。
这道题也可以使用递归的思想。
解题思路：
先定义一个哑节点（注意哑节点的值不能再测试样例中出现），之后运用快慢指针的思想，按照题目要求只改变指针的指向即可。
优解代码及分析：
优解代码（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return head
if head.next and (head.val == head.next.val):
while (head.next != None) and (head.val == head.next.val):
head = head.next
return self.deleteDuplicates(head.next)
else:
head.next = self.deleteDuplicates(head.next)
return head
分析：
这种解法使用了递归的思想，对链表层层递归即可。
No.83.删除排序链表中的重复元素
难度：简单
题目描述：
题解代码（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(-999)
dummy.next = head
slow = dummy
fast =dummy.next
while fast:
if slow.val != fast.val:
slow =slow.next
slow.val = fast.val
fast = fast.next
slow.next = None
return head
或许有用的知识点：
当处理链表且需要考虑空链表时，我们或许可以设置一个哑结点，即dummy=LIstNode（-999），dummy.next = head。
这道题可以用快慢指针的思想。
这道题也可以使用递归的思想。
解题思路：
这道题和上一道题‘No.82.删除排序链表中的重复元素Ⅱ’思路差不多，可以说是上一道题‘No.82.删除排序链表中的重复元素Ⅱ’的阉割版。先定义一个哑节点（注意哑节点的值不能再测试样例中出现），之后运用快慢指针的思想，按照题目要求只改变指针的指向即可。
优解代码及分析：
优解代码（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return head
if head.next and (head.val == head.next.val):
while head.next and (head.val == head.next.val):
head = head.next
return self.deleteDuplicates(head)
else:
head.next = self.deleteDuplicates(head.next)
return head
分析：
这道题和上一道题‘No.82.删除排序链表中的重复元素Ⅱ’思路差不多，可以说是上一道题‘No.82.删除排序链表中的重复元素Ⅱ’的阉割版。这种解法使用了递归的思想，对链表层层递归即可。
No.84.柱状图中最大的矩形
难度：困难
题目描述：
题解代码（Python3.8）
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
heights = [0] + heights + [0]
res = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
#print('储存索引的栈',stack,'其栈顶元素',heights[stack[-1]],'>当前元素',heights[i])
tmp = stack.pop()
#print('判断以原栈顶元素',heights[tmp],'为左端元素向右平移得到的矩形面积',(i-stack[-1]-1)*heights[tmp],'是否比res',res,'大，更新res')
res = max(res,(i-stack[-1]-1)*heights[tmp])
stack.append(i)
#print('将当前元素',heights[i],'入栈,此时储存索引的栈',stack,'保证了栈仍为递增栈')
#print('------------- i++ ------------')
return res
或许有用的知识点：
这道题要用到单调栈的思想。
解题思路：
这道题可以用单调递增栈的思想，所谓用单调递增栈解决这道题，其实可以把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最高的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那么就再次保证了木板是递增的，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。
以heights=[2,1,5,6,2,3]为例，将代码连带注释一起在IDLE运行的逐步结果如下：
No.85.最大矩形
难度：困难
题目描述：
题解代码（Python3.8）
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if (not matrix) or (not matrix[0]):
return 0
l_row = len(matrix)
l_col = len(matrix[0])
heights = [0]*(l_col+2)
res = 0
for i in range(l_row):
stack = []
for j in range(l_col):
if matrix[i][j] == '1':
heights[j+1] += 1
else:
heights[j+1] =0
#print('以第',i,'行为底，其高度数组heights为',heights)
#以下同上一题‘No.84.柱状图中最大的矩形’
for j in range(l_col+2):
while stack and heights[stack[-1]] > heights[j]:
#print('储存索引的栈',stack,'其栈顶元素',heights[stack[-1]],'>当前元素',heights[j])
tmp = stack.pop()
#print('判断以原栈顶元素',heights[tmp],'为左端元素向右平移得到的矩形面积',(j-stack[-1]-1)*heights[tmp],'是否比res',res,'大，更新res')
res = max(res,(j-stack[-1]-1)*heights[tmp])
stack.append(j)
#print('将当前元素',heights[j],'入栈,此时储存索引的栈',stack,'保证了栈仍为递增栈')
#print('------------- j++ -------------')
return res
或许有用的知识点：
这道题要用到单调栈的思想。
解题思路：
这道题其实和上一道题‘No.84.柱状图中最大的矩形’的解题思路很类似，在0-1二维矩阵中，逐行为底将0-1二维矩阵转换成直方柱的形式，每行解法和上一道题‘No.84.柱状图中最大的矩形’就一样了，如下图：
这道题可以用单调递增栈的思想，所谓用单调递增栈解决这道题，其实可以把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最高的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那么就再次保证了木板是递增的，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。
以代码中的matrix（同题目样例）为例，将代码连带注释一起在IDLE运行，运行的代码和代码每一行运行的逐步结果如下：
