題目列表

1. 20. 有效的括號 簡單難度 leetcode鏈接

2. 155. 最小棧 中等難度 leetcode鏈接

3. 394. 字符串解碼 中等難度 leetcode鏈接

4. 739. 每日溫度 中等難度 leetcode鏈接

5. 84. 柱狀圖中最大的矩形 困難難度 leetcode鏈接

題目

（1）有效的括號

題目

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。

2. 左括號必須以正確的順序閉合。

3. 每個右括號都有一個對應的相同類型的左括號。

示例 1：

輸入：s = "()"

輸出：true

示例 2：

輸入：s = "()[]{}"

輸出：true

示例 3：

輸入：s = "(]"

輸出：false

示例 4：

輸入：s = "([])"

輸出：true

示例 5：

輸入：s = "([)]"

輸出：false

提示：

• 1 <= s.length <= 10(4)

• s 僅由括號 '()[]{}' 組成

思路

class Solution:def isValid(self, s: str) -> bool:stack = []for item in s:if item == '(':stack.append(')')elif item == '{':stack.append('}')elif item == '[':stack.append(']')elif not stack or stack[-1] != item:return Falseelse:stack.pop()return True if not stack else False

（2）最小棧

題目

設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的棧。

實現 MinStack 類:

• MinStack() 初始化堆棧對象。

• void push(int val) 將元素val推入堆棧。

• void pop() 刪除堆棧頂部的元素。

• int top() 獲取堆棧頂部的元素。

• int getMin() 獲取堆棧中的最小元素。

示例 1:

輸入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 輸出： [null,null,null,null,-3,null,0,-2]

解釋： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

提示：

• -2(31) <= val <= 2(31) - 1

• pop、top 和 getMin 操作總是在 非空棧 上調用

• push, pop, top, and getMin最多被調用 3 * 10(4) 次

思路

class MinStack(object):def __init__(self):"""initialize your data structure here."""self.stack = []def push(self, x):""":type x: int:rtype: void"""if not self.stack:self.stack.append((x, x))else:self.stack.append((x, min(x, self.stack[-1][1])))def pop(self):""":rtype: void"""self.stack.pop()def top(self):""":rtype: int"""return self.stack[-1][0]def getMin(self):""":rtype: int"""return self.stack[-1][1]# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

（3）字符串解碼

題目

給定一個經過編碼的字符串，返回它解碼后的字符串。

編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次。注意 k 保證為正整數。

你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。

此外，你可以認為原始數據不包含數字，所有的數字只表示重復的次數 k ，例如不會出現像 3a 或 2[4] 的輸入。

測試用例保證輸出的長度不會超過 10(5)。

示例 1：

輸入：s = "3[a]2[bc]" 輸出："aaabcbc"

示例 2：

輸入：s = "3[a2[c]]" 輸出："accaccacc"

示例 3：

輸入：s = "2[abc]3[cd]ef" 輸出："abcabccdcdcdef"

示例 4：

輸入：s = "abc3[cd]xyz" 輸出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30

• s 由小寫英文字母、數字和方括號 '[]' 組成

• s 保證是一個 有效 的輸入。

• s 中所有整數的取值范圍為 [1, 300]

思路

class Solution:def decodeString(self, s: str) -> str:stack, res, multi = [], "", 0for c in s:if c == '[':stack.append([multi, res])res, multi = "", 0elif c == ']':cur_multi, last_res = stack.pop()res = last_res + cur_multi * reselif '0' <= c <= '9':multi = multi * 10 + int(c)  # 比如case：s ="100[leetcode]"else:res += creturn res# 鏈接：https://leetcode.cn/problems/decode-string/solutions/19447/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
# 輔助棧方法：
## 時間復雜度 O(N)，一次遍歷 s
## 空間復雜度 O(N)，輔助棧在極端情況下需要線性空間，例如 2[2[2[a]]]

（4）每日溫度

題目

給定一個整數數組 temperatures ，表示每天的溫度，返回一個數組 answer ，其中 answer[i] 是指對于第 i 天，下一個更高溫度出現在幾天后。如果氣溫在這之后都不會升高，請在該位置用 0 來代替。

示例 1:

輸入: temperatures = [73,74,75,71,69,72,76,73] 輸出: [1,1,4,2,1,1,0,0]

示例 2:

輸入: temperatures = [30,40,50,60] 輸出: [1,1,1,0]

示例 3:

輸入: temperatures = [30,60,90] 輸出: [1,1,0]

提示：

• 1 <= temperatures.length <= 10(5)

• 30 <= temperatures[i] <= 100

思路

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:answer = [0]*len(temperatures)stack = [0]for i in range(1,len(temperatures)):# 情況一和情況二if temperatures[i]<=temperatures[stack[-1]]:stack.append(i)# 情況三else:while len(stack) != 0 and temperatures[i]>temperatures[stack[-1]]:answer[stack[-1]]=i-stack[-1]stack.pop()stack.append(i)return answer

（5）柱形圖中最大的矩形

題目

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例 1:

輸入：heights = [2,1,5,6,2,3] 輸出：10 解釋：最大的矩形為圖中紅色區域，面積為 10

示例 2：

輸入： heights = [2,4] 輸出： 4

提示：

• 1 <= heights.length <=10(5)

• 0 <= heights[i] <= 10(4)

思路

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:# 單調棧'''找每個柱子左右側的第一個高度值小于該柱子的柱子單調棧：棧頂到棧底：從大到小（每插入一個新的小數值時，都要彈出先前的大數值）棧頂，棧頂的下一個元素，即將入棧的元素：這三個元素組成了最大面積的高度和寬度情況一：當前遍歷的元素heights[i]大于棧頂元素的情況情況二：當前遍歷的元素heights[i]等于棧頂元素的情況情況三：當前遍歷的元素heights[i]小于棧頂元素的情況'''# 輸入數組首尾各補上一個0（與42.接雨水不同，本題原首尾兩個柱子可以作為核心柱進行最大面積嘗試）heights.insert(0, 0) # 關鍵代碼heights.append(0)stack = [0]result = 0for i in range(1, len(heights)):# 情況一if heights[i] > heights[stack[-1]]:stack.append(i)# 情況二elif heights[i] == heights[stack[-1]]:stack.pop()stack.append(i)# 情況三else:# 拋出所有較高的柱子while stack and heights[i] < heights[stack[-1]]:# 棧頂就是中間的柱子，主心骨mid_index = stack[-1]stack.pop()if stack:left_index = stack[-1]right_index = iwidth = right_index - left_index - 1height = heights[mid_index]result = max(result, width * height)stack.append(i)return result

結尾

親愛的讀者朋友：感謝您在繁忙中駐足閱讀本期內容！您的到來是對我們最大的支持??

正如古語所言："當局者迷，旁觀者清"。您獨到的見解與客觀評價，恰似一盞明燈💡，能幫助我們照亮內容盲區，讓未來的創作更加貼近您的需求。

若此文給您帶來啟發或收獲，不妨通過以下方式為彼此搭建一座橋梁： ? 點擊右上角【點贊】圖標，讓好內容被更多人看見 ? 滑動屏幕【收藏】本篇，便于隨時查閱回味 ? 在評論區留下您的真知灼見，讓我們共同碰撞思維的火花

我始終秉持匠心精神，以鍵盤為犁鏵深耕知識沃土💻，用每一次敲擊傳遞專業價值，不斷優化內容呈現形式，力求為您打造沉浸式的閱讀盛宴📚。

有任何疑問或建議？評論區就是我們的連心橋！您的每一條留言我都將認真研讀，并在24小時內回復解答📝。

愿我們攜手同行，在知識的雨林中茁壯成長🌳，共享思想綻放的甘甜果實。下期相遇時，期待看到您智慧的評論與閃亮的點贊身影?！

萬分感謝🙏🙏您的點贊👍👍、收藏?🌟、評論💬🗯?、關注??💚

---

自我介紹：一線互聯網大廠資深算法研發（工作6年+），4年以上招聘面試官經驗（一二面面試官，面試候選人400+），深諳崗位專業知識、技能雷達圖，已累計輔導15+求職者順利入職大中型互聯網公司。熟練掌握大模型、NLP、搜索、推薦、數據挖掘算法和優化，提供面試輔導、專業知識入門到進階輔導等定制化需求等服務，助力您順利完成學習和求職之旅（有需要者可私信聯系）?

友友們，自己的知乎賬號為“快樂星球”，定期更新技術文章，敬請關注！