給定一個整數數組 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]

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:# 1.從右到左# st = []  # 存儲的是下標# ans = [0] * len(temperatures)# for i in range(len(temperatures) - 1, -1, -1):#     t = temperatures[i]#     while st and temperatures[st[-1]] <= t:#         # 如果棧中有元素且棧口溫度小于等于當前溫度，則棧口的溫度不可能是前面溫度的答案，彈出#         st.pop()#     # 如果棧不為空，說明后面存在比當前溫度高的溫度，記錄答案#     if st:#         ans[i] = st[-1] - i#     # 當前溫度進棧#     st.append(i)# return ans# 2.從左到右st = []     # 棧內存儲的是還沒記錄答案的每日溫度ans = [0] * len(temperatures)for i, t in enumerate(temperatures):# 如果棧不為空且當前溫度大于棧口元素，說明當前溫度是棧口溫度的答案while st and t > temperatures[st[-1]]:ans[st[-1]] = i - st[-1]st.pop()# 進棧st.append(i)return ans# 第一種做法相當于每輪循環都會記錄當天的答案# 第二種做法相當于只有在彈出棧時才記錄答案

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。 

示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

class Solution:def trap(self, height: List[int]) -> int:# 橫著看，當前柱子什么時候能接水？# 當后面柱子的高度超過當前柱子的高度時，就能接水了st = []  # 棧內元素單調遞增s = 0for i, right_h in enumerate(height):while st and height[st[-1]] < right_h:# 如果當前柱子高度大于棧口元素高度，說明棧口元素的柱子是能接水的mid_h = height[st.pop()]  # 棧口元素高度# 如果棧中沒有柱子了，那水會從左邊流出去，退出if not st:breakleft_h = height[st[-1]]  # 左邊數字的高度w = i - st[-1] - 1  # 寬度h = min(left_h, right_h) - mid_h  # 高度s += w * h  # 面積st.append(i)return s

nums1 中數字 x 的 下一個更大元素 是指 x 在 nums2 中對應位置 右側 的 第一個 比 x 大的元素。

給你兩個 沒有重復元素 的數組 nums1 和 nums2 ，下標從 0 開始計數，其中nums1 是 nums2 的子集。

對于每個 0 <= i < nums1.length ，找出滿足 nums1[i] == nums2[j] 的下標 j ，并且在 nums2 確定 nums2[j] 的 下一個更大元素 。如果不存在下一個更大元素，那么本次查詢的答案是 -1 。

返回一個長度為 nums1.length 的數組 ans 作為答案，滿足 ans[i] 是如上所述的 下一個更大元素 。

示例 1：

輸入：nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出：[-1,3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：
- 4 ，用加粗斜體標識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
- 1 ，用加粗斜體標識，nums2 = [1,3,4,2]。下一個更大元素是 3 。
- 2 ，用加粗斜體標識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。

示例 2：

輸入：nums1 = [2,4], nums2 = [1,2,3,4].
輸出：[3,-1]
解釋：nums1 中每個值的下一個更大元素如下所述：
- 2 ，用加粗斜體標識，nums2 = [1,2,3,4]。下一個更大元素是 3 。
- 4 ，用加粗斜體標識，nums2 = [1,2,3,4]。不存在下一個更大元素，所以答案是 -1 。

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:idx = {x: i for i, x in enumerate(nums1)}st = []ans = [-1] * len(nums1)# 1.從左向右# for i, x in enumerate(nums2):#     # 如果當前元素大于棧口元素，說明可以記錄在棧口的答案了#     while st and x > nums2[st[-1]]:#         j = st.pop()#         if nums2[j] in idx:     # 如果棧口元素在nums1中#             ans[idx[nums2[j]]] = x  # 記錄答案#     st.append(i)    # 元素進棧# return ans# 2.從右到左for i in range(len(nums2) - 1, -1, -1):num = nums2[i]# 如果當前元素大于等于棧口元素，說明棧口的元素永遠不可能是前面元素的答案，出棧while st and num >= nums2[st[-1]]:st.pop()# 如果棧不為空，此時棧口元素大于當前元素，說明可以記錄當前元素的答案了if st and num in idx:ans[idx[num]] = nums2[st[-1]]st.append(i)    # 元素進棧return ans

給定一個循環數組 nums （ nums[nums.length - 1] 的下一個元素是 nums[0] ），返回 nums 中每個元素的 下一個更大元素 。

數字 x 的 下一個更大的元素 是按數組遍歷順序，這個數字之后的第一個比它更大的數，這意味著你應該循環地搜索它的下一個更大的數。如果不存在，則輸出 -1 。

示例 1:

輸入: nums = [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數是 2；
數字 2 找不到下一個更大的數； 
第二個 1 的下一個最大的數需要循環搜索，結果也是 2。

示例 2:

輸入: nums = [1,2,3,4,3]
輸出: [2,3,4,-1,4]

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:# 循環兩遍元素，確保下一個更大元素在循環搜索中發現st = []ans = [-1] * len(nums)n = len(nums)# 1. 從左向右# for i in range(n * 2):#     num = nums[i % n]#     while st and num > nums[st[-1]]:#         j = st.pop()#         ans[j] = num#     st.append(i % n)# return ans# 2.從右向左for i in range(n * 2 - 1, -1, -1):num = nums[i % n]while st and num >= nums[st[-1]]:st.pop()if st:ans[i % n] = nums[st[-1]]st.append(i % n)return ans

給你一個數組 prices ，其中 prices[i] 是商店里第 i 件商品的價格。

商店里正在進行促銷活動，如果你要買第 i 件商品，那么你可以得到與 prices[j] 相等的折扣，其中 j 是滿足 j > i 且 prices[j] <= prices[i] 的 最小下標 ，如果沒有滿足條件的 j ，你將沒有任何折扣。

請你返回一個數組，數組中第 i 個元素是折扣后你購買商品 i 最終需要支付的價格。

示例 1：

輸入：prices = [8,4,6,2,3]
輸出：[4,2,4,2,3]
解釋：
商品 0 的價格為 price[0]=8 ，你將得到 prices[1]=4 的折扣，所以最終價格為 8 - 4 = 4 。
商品 1 的價格為 price[1]=4 ，你將得到 prices[3]=2 的折扣，所以最終價格為 4 - 2 = 2 。
商品 2 的價格為 price[2]=6 ，你將得到 prices[3]=2 的折扣，所以最終價格為 6 - 2 = 4 。
商品 3 和 4 都沒有折扣。

示例 2：

輸入：prices = [1,2,3,4,5]
輸出：[1,2,3,4,5]
解釋：在這個例子中，所有商品都沒有折扣。

示例 3：

輸入：prices = [10,1,1,6]
輸出：[9,0,1,6]

class Solution:def finalPrices(self, prices: List[int]) -> List[int]:st = []ans = prices.copy()# 1.從左到右# for i, x in enumerate(prices):#     while st and x <= prices[st[-1]]:#         j = st.pop()#         ans[j] = prices[j] - x#     st.append(i)# return ans# 2.從右到左for i in range(len(prices) - 1, -1, -1):while st and prices[i] < prices[st[-1]]:st.pop()if st:ans[i] = prices[i] - prices[st[-1]]st.append(i)return ans

設計一個算法收集某些股票的每日報價，并返回該股票當日價格的 跨度 。

當日股票價格的 跨度 被定義為股票價格小于或等于今天價格的最大連續日數（從今天開始往回數，包括今天）。

• 例如，如果未來 7 天股票的價格是 [100,80,60,70,60,75,85]，那么股票跨度將是 [1,1,1,2,1,4,6] 。

實現 StockSpanner 類：

• StockSpanner() 初始化類對象。
• int next(int price) 給出今天的股價 price ，返回該股票當日價格的 跨度 。

示例：

輸入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
輸出：
[null, 1, 1, 1, 2, 1, 4, 6]解釋：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80);  // 返回 1
stockSpanner.next(60);  // 返回 1
stockSpanner.next(70);  // 返回 2
stockSpanner.next(60);  // 返回 1
stockSpanner.next(75);  // 返回 4 ，因為截至今天的最后 4 個股價 (包括今天的股價 75) 都小于或等于今天的股價。
stockSpanner.next(85);  // 返回 6

# 往回找小于等于今天價格的連續日期，其實就是找上一個更大元素
class StockSpanner:def __init__(self):self.st = []self.prices = []def next(self, price: int) -> int:self.prices.append(price)# 1. 從左到右# 如果當前元素大于等于棧口元素，那么將棧口元素出棧# 如果當前元素小于棧口元素，那么記錄當前元素的答案while self.st and price >= self.prices[self.st[-1]]:# 如果當前股票價格大于棧口元素，那么永遠不可能是后面元素的答案，彈出self.st.pop()if self.st:ans = len(self.prices) - self.st[-1] - 1else:# 如果棧沒元素了，說明前面的股票都大于等于當前股票ans = len(self.prices)self.st.append(len(self.prices) - 1)return ans# 2.從右到左# 如果當前元素大于棧口元素，說明棧口的元素找到答案了，記錄并彈出# 如果當前元素小于等于棧口元素，則進棧# 但由于此題是每天都要返回一次答案，這種思路是只有當當前元素大于棧口元素了，才能返回棧口元素的答案# 所以此題只能按照從右到左的思路# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

給定一個長度為 n 的鏈表 head

對于列表中的每個節點，查找下一個 更大節點 的值。也就是說，對于每個節點，找到它旁邊的第一個節點的值，這個節點的值 嚴格大于 它的值。

返回一個整數數組 answer ，其中 answer[i] 是第 i 個節點( 從1開始 )的下一個更大的節點的值。如果第 i 個節點沒有下一個更大的節點，設置 answer[i] = 0 。

示例 1：

輸入：head = [2,1,5]
輸出：[5,5,0]

示例 2：

輸入：head = [2,7,4,3,5]
輸出：[7,0,5,5,0]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:st = []     # 棧里面存儲的是（下標，節點值）ans = []# 從左到右# 如果當前元素大于棧口元素，說明棧口的元素找到答案了，記錄并彈出# 如果當前元素小于等于棧口元素，說明還沒有找到答案，進棧while head:ans.append(0)  # 占位while st and head.val > st[-1][1]:j, val = st.pop()ans[j] = head.valst.append((len(ans) - 1, head.val))head = head.nextreturn ans