php租车网站北京vi设计公司北京广告设计公司

4.9 单调栈与单调队列（基础题）

  很有趣的两个数据结构。
原视频讲解链接

单调栈

739. 每日温度

题目链接
给定一个整数数组 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, temp: List[int]) -> List[int]:"""时间复杂度：O(n)，其中n为temperatures的长度。空间复杂度：O(n)。"""n = len(temp)ans = [0] * nst = [] # to do listfor i,t in enumerate(temp):while st and t > temp[st[-1]]:j = st.pop()ans[j] = i - jst.append(i)return ans

42. 接雨水

题目链接
给定 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

提示：

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

class Solution:def trap(self, height: List[int]) -> int:"""单调栈解法时间复杂度：O(n)，其中n为height的长度。空间复杂度：O(min(n,U))，其中U=max(height)−min(height)+1。注意栈中没有重复元素，在height值域很小的情况下，空间复杂度主要取决于height的值域范围。"""ans = 0st = []for i,h in enumerate(height):while st and h >= height[st[-1]]:bottom_h = height[st.pop()]if not st:breakleft = st[-1]dh = min(height[left],h) - bottom_hans += dh * (i - left - 1)st.append(i)return ans    

单调队列

239. 滑动窗口最大值

题目链接
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：
输入：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

示例 2：
输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:"""时间复杂度：O(n)，其中 n 为 nums 的长度。由于每个下标至多入队出队各一次，所以二重循环的循环次数是 O(n) 的。空间复杂度：O(min(k,U))，其中 U 是 nums 中的不同元素个数（本题至多为 20001）。双端队列至多有 k 个元素，同时又没有重复元素，所以也至多有 U 个元素，所以空间复杂度为 O(min(k,U))。返回值的空间不计入。"""ans = []q = deque()for i, x in enumerate(nums):# Enterwhile q and nums[q[-1]] < x:q.pop()q.append(i)# Leaveif i - q[0] >= k:q.popleft()# Recordif i >= k - 1:ans.append(nums[q[0]])return ans