預習題目
有效的模板字符串
最小棧

實戰題目
最大矩形面積
滑動窗口

課后作業
用 add first 或 add last 這套新的 API 改寫 Deque 的代碼
分析 Queue 和 Priority Queue 的源碼
設計環形隊列
雨水

小結
把問題簡單抽象化
比如求雨水的，簡化邏輯為裝滿的情況下每個柱子距離水平面的距離，進而求出每個柱子對水的容納，直接從最終狀態進行分解，然后通過解決子問題來解決整個問題
求最大矩形面積，簡化為以每個柱子作為矩形的最低高度，進行狀態搜索，這個是枚舉所有的狀態，找到最優的狀態
問題簡化為可以枚舉的狀態，那么計算機就能夠對這些狀態進行單個處理，進而得到結果

算法的一個思想就是在解空間進行搜索，所以，對于復雜的問題可以嘗試進行解空間的劃分，然后進行搜索，得到最優，也就是枚舉
但是矩形這道題還有一種是枚舉兩個邊界，找中間最小的柱子，這種枚舉方式可能也不容易處理，這個也是在解空間進行搜索，都是問題的解決方案

有時候有的問題可能很快的抽象為簡單的問題，但是有點問題邏輯比較復雜，更難抽象為獨立的簡單的問題，所以處理的方式也不太一樣,有些問題，初始的時候想不到解決方法也很正常，因為你連最基本的暴力方法都沒有解決的頭緒，所以處理起來也更加復雜化。所以還是要多看多練習，逐步提升對同類問題的抽象轉化能力。

矩形和雨水問題是很好的思想轉化的題目，可以多學習和體會。

collections-deque

from collections import dequeappend(x) Add x to the right side of the deque.appendleft(x) Add x to the left side of the deque.clear() Remove all elements from the deque leaving it with length 0.count(x) Count the number of deque elements equal to x.New in version 2.7.extend(iterable) Extend the right side of the deque by appending elements from the iterable argument.extendleft(iterable) Extend the left side of the deque by appending elements from iterable. Note, the series of left appends results in reversing the order of elements in the iterable argument.pop() Remove and return an element from the right side of the deque. If no elements are present, raises an IndexError.popleft() Remove and return an element from the left side of the deque. If no elements are present, raises an IndexError.remove(value) Remove the first occurrence of value. If not found, raises a ValueError.New in version 2.5.reverse() Reverse the elements of the deque in-place and then return None.New in version 2.7.rotate(n=1) Rotate the deque n steps to the right. If n is negative, rotate to the left.In addition to the above, deques support iteration, pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), membership testing with the in operator, and subscript references such as d[-1]. Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.樣例使用雙端隊列，結合后面的大的可以覆蓋前面的小的模式，這個問題一下就迎刃而解了，真是神奇啊加油from collections import dequeclass Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:## 雙端隊列模式n = len(nums)dq = deque()for i in range(k) :while dq and nums[dq[-1]] <= nums[i] :dq.pop()dq.append(i)res = []res.append(nums[dq[0]])for j in range(k,n) :if (j - dq[0]) >= k :dq.popleft()while dq and nums[dq[-1]] <= nums[j] :dq.pop()dq.append(j)res.append(nums[dq[0]])return res

heapq

heapq.heappush(heap, item) Push the value item onto the heap, maintaining the heap invariant.heapq.heappop(heap) Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].heapq.heappushpop(heap, item) Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().New in version 2.6.heapq.heapify(x) Transform list x into a heap, in-place, in linear time.heapq.heapreplace(heap, item)樣例 class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:## 堆的應用n = len(nums)res = []heap = [(-nums[i],i) for i in range(k)]heapq.heapify(heap)res.append(-heap[0][0])for i in range(k,n):heapq.heappush(heap,(-nums[i],i))while (i - heap[0][1]) >= k :heapq.heappop(heap)res.append(-heap[0][0])return res

總結

以上是生活随笔為你收集整理的算法训练营04-map,set,dequeue,stack的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。