他向远方望去，无法看到高山背后的矮山，只能看到一座座更高的山峰。

推荐先做做 8.【题单】常用数据结构 中的「枚举右，维护左」再来刷本题单。

及时去掉无用数据，保证栈中数据有序

1. 739. 每日温度

   从右往左写法，每次循环必定计算一个答案

   class Solution:
   def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
       n = len(temperatures)
       ans = [0] * n
       st = []
       for i in range(n - 1, -1, -1):
           while st and temperatures[i] >= temperatures[st[-1]]:
               st.pop()
           if st:
               ans[i] = st[-1] - i
           st.append(i)
       return ans

   时间复杂度：O(n)，其中 n 为 temperatures 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。

   空间复杂度：O(min(n,U))，其中 U=max(temperatures)−min(temperatures)+1。返回值不计入，仅考虑栈的最大空间消耗

   从左往右写法，栈里存储的都是没有找到答案的数，一但找到一个比他们大的，就弹出栈内小的元素，然后更新答案。可能执行多次循环才能找到答案，并一个计算出多个答案

   class Solution:
   def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
       n = len(temperatures)
       ans = [0] * n
       st = []
       for i in range(n):
           while st and temperatures[i] > temperatures[st[-1]]:
               j = st.pop()
               ans[j] = i - j
           st.append(i)
       return ans

   时间复杂度：O(n)

   空间复杂度：O(n)。注意这种写法栈中可以有重复元素。

2. 1475. 商品折扣后的最终价格

   class Solution:
   def finalPrices(self, prices: List[int]) -> List[int]:
       res = prices
       st = []
       for i, price in enumerate(prices):
           while st and price <= prices[st[-1]]:
               j = st.pop()
               res[j] = prices[j] - price
           st.append(i)
       return res

   时间复杂度：O(n)

   空间复杂度：O(n)

3. 496. 下一个更大元素 I

   先计算nums2中各个元素的下一个更大元素，再遍历 nums1 写回答案的做法。但是当nums1只有一个元素，nums2有10^4个元素，这时间复杂度就高得离谱了

   class Solution:
   def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
       dic = {}
       st = []
       res = []
       # 先计算nums2中各个元素的下一个更大元素
       for i in range(len(nums2)):
           while st and nums2[i] > nums2[st[-1]]:
               j = st.pop()
               dic[nums2[j]] = nums2[i]
           st.append(i)
       # 再遍历 nums1 写回答案
       for i, num in enumerate(nums1):
           if num in dic:
               res.append(dic[num]) 
           else:
               res.append(-1) 
       return res

   时间复杂度：O(n + m)，其中 n 是 nums1 的长度，m 是 nums2 的长度。

   空间复杂度：O(n + m)

   优化：可以只把 nums1 的元素入栈，在 nums2 中查找 nums1 元素后的第一个最大值

   class Solution:
   def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
       dic = {num: i for i, num in enumerate(nums1)}
       st = []
       res = [-1] * len(nums1)
       for num in nums2:
           while st and num > st[-1]:
               j = st.pop()
               res[dic[j]] = num
           if num in dic:
               st.append(num) # 只把在 nums1 中的元素入栈
       return res

   时间复杂度：O(n + m)，其中 n 是 nums1 的长度，m 是 nums2 的长度。

   空间复杂度：O(n + m)

4. 503. 下一个更大元素 II

   简单粗暴直接把单调栈用两次

   class Solution:
   def nextGreaterElements(self, nums: List[int]) -> List[int]:
       n = len(nums)
       res = [-1] * n
       st = []
       for i, num in enumerate(nums):
           while st and num > nums[st[-1]]:
               j = st.pop()
               res[j] = num
           st.append(i)
       for i, num in enumerate(nums):
           while st and num > nums[st[-1]]:
               j = st.pop()
               res[j] = num
           st.append(i)
       return res

   时间复杂度：O(n)，其中 n 是 nums 的长度。

   空间复杂度：O(n)

   优化：使用 % 来合并两个循环

   class Solution:
   def nextGreaterElements(self, nums: List[int]) -> List[int]:
       n = len(nums)
       res = [-1] * n
       st = []
       for i in range(2 * n):
           while st and nums[i % n] > nums[st[-1]]:
               j = st.pop()
               res[j] = nums[i % n]
           st.append(i % n)
       return res

   时间复杂度：O(n + m)，其中 n 是 nums1 的长度，m 是 nums2 的长度。

   空间复杂度：O(n + m)

5. 1019. 链表中的下一个更大节点

   因为链表没法确定res的小标，可以在栈内存储一个元组，同时记录下标和值；元组内的元素不可修改，但是整体可以被 pop 弹出

   # 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]:
       res = []
       st = [] # (索引, 值) (0, 2)
       cur = head
       while cur:
           while st and cur.val > st[-1][1]:
               j = st.pop()[0]
               res[j] = cur.val
           st.append((len(res), cur.val))
           res.append(0)
           cur = cur.next
       return res

   时间复杂度：O(n)，其中 n 是 nums 的长度。

   空间复杂度：O(n)

6. 962. 最大宽度坡

   class Solution:
   def maxWidthRamp(self, nums: List[int]) -> int:
       # nums = [6,0,8,2,1,5]
       n = len(nums)
       st = []
       res = 0
       # 从左往右构造一个单调递减栈 [0, 1] 对应 [6, 0]
       # 如果 8 也加入栈，能在后面找到比 8 大的元素，一定比 6 和 0 大，所以构造单调递减栈
       for i, num in enumerate(nums):
           while not st or num < nums[st[-1]]:
               st.append(i)
       # 从右往左找到第一个比栈顶大的，作为预备宽度最大值
       for j in range(n - 1, -1, -1):
           while st and nums[j] >= nums[st[-1]]:
               res = max(res, j - st.pop())
       return res

   时间复杂度：O(n)，其中 n 是 nums 的长度。

   空间复杂度：O(n)

7. 853. 车队

   看不懂

   时间复杂度：O(n)

   空间复杂度：O(n)

8. 901. 股票价格跨度

   class StockSpanner:
   
   def __init__(self):
       self.st = [(-1, inf)]
       self.i = -1
   
   
   def next(self, price: int) -> int:
       self.i += 1
       while self.st[-1][1] <= price:
           self.st.pop()
       self.st.append((self.i, price))
       return self.i - self.st[-2][0]
   
   
   # Your StockSpanner object will be instantiated and called as such:
   # obj = StockSpanner()
   # param_1 = obj.next(price)

   时间复杂度：均摊 O(1)。因为每个元素至多入栈出栈各一次。

   空间复杂度：O(min(q,U))。其中 q 为 next 的调用次数，U 为 price 的范围。注意栈中没有重复元素，在 price 值域很小的情况下，空间复杂度主要取决于 price 的值域范围。