在线设计网站海报,wordpress插件 悬浮,免费网站电视剧全免费的app,网站建设公司好文章目录 4.9 单调栈与单调队列#xff08;基础题#xff09;单调栈739. 每日温度42. 接雨水单调队列239. 滑动窗口最大值 4.9 单调栈与单调队列#xff08;基础题#xff09; 很有趣的两个数据结构。 原视频讲解链接
单调栈 739. 每日温度
题目链接 给定一个整数数组 te… 文章目录 4.9 单调栈与单调队列基础题单调栈739. 每日温度42. 接雨水单调队列239. 滑动窗口最大值 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^530 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 ans42. 接雨水
题目链接 给定 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.length1 n 2 * 10^40 height[i] 10^5
class Solution:def trap(self, height: List[int]) - int:单调栈解法时间复杂度O(n)其中n为height的长度。空间复杂度O(min(n,U))其中Umax(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^41 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
