特點是隻能從一端（棧頂）操作元素，先進後出（FILO），操作主要包含出棧 ；入棧；獲取棧頂元素；判斷棧是否已滿（數組棧）；判斷棧是否為空棧。

• 邏輯結構

• 分類
• 數組棧
• 棧的空間大小固定并且需要一次性申請。
• 需要使用一個指針指向棧頂位置；棧為空時指針指向-1。
• 鍊表棧
• 棧空間上限取決于内存空間。
• 入棧和出棧操作在鍊表的頭指針處，時間複雜度為O(1)。
• 示例

設計一個棧，除了常規棧支持的pop與push函數以外，還支持min函數，該函數返回棧元素中的最小值。執行push、pop和min操作的時間複雜度必須為O(1)。

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

class MinStack(object): def __init__(self): """ initialize your data structure here. s: 數組棧 m: 棧s中的最小元素 t: 臨時棧,s的輔助棧 pop操作由于将s中元素壓入到t中，所以時間複雜度為O(n); push和getMin操作時間複雜度為O(1) """ self.s = [] self.m = None self.t = [] def push(self, x): """ :type x: int :rtype: None 入棧 1: 如果x為第一個入棧元素，則為最小值，将x賦值給m 2: x < m 說明剛入棧的元素x為最小值，将x賦值給m """ # x入棧 self.s.append(x) if self.m is None: self.m = x else: if self.m > x: self.m = x def pop(self): """ :rtype: None 出棧 1: 如果s棧頂元素不是最小元素，則直接彈出s棧頂元素 2: s棧頂元素為最小元素: 2.1 将s中剩餘元素的棧頂元素賦值給m（當作最小元素） 2.2 将s中元素依次壓入t中，并與m比較，将小的值記錄到m中 2.3 将t中元素壓入s中 m記錄的為s中剩餘元素的最小值 """ r = self.s.pop() if r == self.m: self.m = None if len(self.s): self.m = self.s[-1] while len(self.s): if self.s[-1] < self.m: self.m = self.s[-1] self.t.append(self.s.pop()) while len(self.t): self.s.append(self.t.pop()) def top(self): """ :rtype: int 返回棧頂元素 """ return self.s[-1] def getMin(self): """ :rtype: int """ return self.m

• 示意圖

隊列

允許從其中一端将元素寫入，從另一端進行移出。特點是先進先出（FIFO）。操作主要包含入隊；出隊；獲取隊首元素；判斷隊列是否已滿（數組隊列）；判斷隊列是否為空。

• 邏輯結構

• 分類
• 數組隊列
• 從數組一端入隊，從另一端進行出隊操作。
• 空隊列存在兩種情況：隊首等于隊尾等于0；隊首等于隊尾等于數組大小（N）-1，使用單獨一個變量标識隊列是滿隊列還是空隊列。
• 循環隊列
• 空出一個空間用來判斷是空隊列還是滿隊列情況（否則空隊列和滿隊列情況時隊首和隊尾指針相同）。
• 空隊列時隊首指針和隊尾指針相同。
• 滿隊列時隊首指針加1模上數組大小（N）等于隊尾指針。
• 鍊表隊列
• 隊首指針指向頭節點；隊尾指針指向尾節點。入隊從頭節點位置操作；出隊從尾節點位置操作。
• 示例

給定一個數組 nums 和滑動窗口的大小 k，請找出所有滑動窗口裡的最大值。

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

輸出: [3,3,5,5,6,7]

解釋:

滑動窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

---

---

---

class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] 列表 :type k: int 窗口大小 :rtype: List[int] 1. 如果t中沒有元素，則将當前下标和元素值組成的元組(idx, nums[idx])追加到t中 2. 如果t中的第一個元素的下标小于當前窗口的最小下标或者第一個元素的值小于當前元素，t執行彈出第一個元素操作，直到不滿足上面兩個條件，将當前元素和下标(idx, nums[idx])追加到t中。 3. 如果當前下标 大于等于k-1,說明在窗口内，将t中的第一個元素的值（當前窗口中最大值）追加到r中。 3.1 追加之前向将隊列中小于當前元素的元素彈出(從右側彈出)。 4. 遍曆數組重複1－3的操作。 """ # 記錄窗口中的元素（元素下标，元素值）:雙端隊列 t = [] # 記錄每個窗口中的最大值 r = [] # 當前遍曆的下标 idx = 0 # 數組nums的長度 l = len(nums) while idx < l: # 判斷條件2和3 # t[0][0] < idx 1 - k : 判斷t中的第一個元素（窗口中的最大值）是否在窗口内，不在窗口内需要移除 # t[0][1] < nums[idx] : 判斷t中第一個元素是否是當前窗口内的最大值，不是的話需要移除；否則将當前窗口中的其它元素追加到t中（不是當前窗口的最大值，可能是下一個窗口的最大值） while t and (t[0][0] < idx 1 - k or t[0][1] < nums[idx]): t.pop(0) # 因為元素會順序追加到t中,，經過上面的判斷，t中的元素都在一個窗口内 # 在追加當前元素之前，先将當前窗口内小于當前元素的元素移除 while t and t[-1][1] < nums[idx]: t.pop() t.append((idx,nums[idx])) # 記錄窗口中的最大值 if idx >= k - 1: r.append(t[0][1]) idx = 1 return r

• 示意圖

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部