-
【LeetCode】滑动窗口、双指针、单调队列和单调栈
2020-06-14 22:55:02单调队列=滑动窗口内的最值 84. 柱状图中最大的矩形 思路: 如何枚举所有的情况?枚举所有柱形的上边界,作为整个矩形的上边界 然后找出左右边界,找出左边离它最近,比它小且最高的矩形;找出右边离它最近,比它小...目录
167. 两数之和 II - 输入有序数组
思路:
- 一般双指针的主要思路是先找到暴力解法,然后考虑有没有单调性之类的性质可以利用,再进行优化
- 使用i,j两个指针,初始位置在0和数组末尾,若相加的结果大于target则说明当前的结果需要减小,则j往前移;若相加的结果小于target则说明当前的结果需要增大,则i往后移。
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: n = len(numbers) i, j = 0, n-1 while i<j: if numbers[i] + numbers[j] < target: i += 1 elif numbers[i] + numbers[j] > target: j -= 1 else: return [i+1, j+1]
88. 合并两个有序数组
思路:
- 这道题就是基本的归并思想
- 由于题目要求的是把结果存入nums1中,则要注意不能从前开始比较合并,要从后面开始
- 这里需要注意的是如果p1,p2赋初值为m-1,n-1,可能就取不到下标为0的那个数
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # nums1的最大数指针 nums2的最大数指针 结果集的最大数指针 p1, p2, p3 = m, n, m+n while p1 and p2: if nums1[p1-1] >= nums2[p2-1]: nums1[p3-1] = nums1[p1-1] p1 -= 1 else: nums1[p3-1] = nums2[p2-1] p2 -= 1 p3 -= 1 while p2: nums1[p3-1] = nums2[p2-1] p2 -= 1 p3 -= 1
26. 删除排序数组中的重复项
思路:
- 由于不能申请额外空间,考虑直接在数组上进行操作。
- 设置两个指针,一个指向当前需要存储数的位置k,一个对数组进行扫描i
class Solution: def removeDuplicates(self, nums: List[int]) -> int: if not nums: return 0 k = 1 for i in range(1, len(nums)): if nums[i] != nums[i-1]: nums[k] = nums[i] k += 1 return k
76. 最小覆盖子串
思路:
- 首先一样的步骤,考虑暴力解法,会需要O(n^2)的时间复杂度
- 然后考虑单调性,我们可以使用两个指针,i,j指示答案字符串的首尾。当i逐渐往后移,j必定只能往后增加,不可能往前,因为那样会包含了最佳答案在里面,不可能得到最短的。
- 这样的话,维护一个hash表,记录t字符串每个字符出现的次数,最后考虑的就是i依次往后遍历,j从起点开始,i往后一格,将hash对应位置-1,j也往后,若当前所指的位置hash表中对应结果小于0了,说明这个字符不在答案中,j往后移
- 再维护一个答案t所需要几个不同的字符,当都得到了,比较一下当前s[j:i+1]的长度,用res记录最短的即是答案
class Solution: def minWindow(self, s: str, t: str) -> str: hash_table = {} for ch in t: hash_table[ch] = hash_table.get(ch, 0) + 1 cnt = len(hash_table.items()) res = "" c, j = 0, 0 for i in range(len(s)): num = hash_table.get(s[i], 0) if num == 1: c += 1 elif num==0: hash_table[s[i]] = hash_table.get(s[i], 0) hash_table[s[i]] -= 1 # j从前往后 while hash_table[s[j]] < 0 and j<i: hash_table[s[j]] += 1 j += 1 if c==cnt: if not res or len(res)>i-j+1: res = s[j:i+1] return res
32. 最长有效括号
思路:
- 首先需要记住括号序列的一个重要性质:假如将(当做数字1,)当做数字-1;则合法的括号序列前缀和一定是>=0的,并且整个序列的最终结果肯定是0
- start枚举当前这一段的开头,cnt记录前缀和。
- 若是当前的cnt<0了,说明这一段是不合法的,start=i+1,cnt=0
- 若是当前的cnt>0,继续做
- 若是当前的cnt==0,说明当前的这一段是合法的,比较和res的长度,若大于则更新res
- 注意,为了防止出现((())这种情况,也就是最后的和不会等于0的情况,所以还需要反过来再做一遍
- (和)的ascii码二进制相差一位,可以直接异或处理
class Solution: def longestValidParentheses(self, s: str) -> int: reverse_s = list(s[::-1]) for index, ch in enumerate(reverse_s): reverse_s[index] = chr(ord(ch)^1) return max(self.work(s), self.work("".join(reverse_s))) def work(self, s): """ 返回当前子串的最长长度 """ start, cnt = 0, 0 n = len(s) res = 0 for i in range(n): if s[i] == "(": cnt += 1 else: cnt -= 1 if cnt < 0: start = i+1 cnt = 0 elif cnt == 0: res = max(res, i-start+1) return res
155. 最小栈
思路:
- 这个题有点类似于前缀和,始终要维护一个前缀和的最小数。
- 用两个栈,一个是模拟栈操作的,一个是始终保存当前栈中最小的数字
class MinStack: def __init__(self): """ initialize your data structure here. """ self.stack = [] self.stack_min = [] def push(self, x: int) -> None: self.stack.append(x) if not self.stack_min: self.stack_min.append(x) else: self.stack_min.append(min(self.stack_min[-1], x)) def pop(self) -> None: self.stack.pop() self.stack_min.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.stack_min[-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()
- tips:单调栈(查找每个数左侧第一个比它小的数);单调队列=滑动窗口内的最值
84. 柱状图中最大的矩形
思路:
- 如何枚举所有的情况?枚举所有柱形的上边界,作为整个矩形的上边界
- 然后找出左右边界,找出左边离它最近,比它小且最高的矩形;找出右边离它最近,比它小且最高的矩形。
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) left, right = [0]*n, [0]*n stk = [] for i in range(n): while stk and heights[stk[-1]]>=heights[i]: stk.pop() if not stk: left[i] = -1 else: left[i] = stk[-1] stk.append(i) while stk: stk.pop() for i in range(n-1, -1, -1): while stk and heights[stk[-1]]>=heights[i]: stk.pop() if not stk: right[i] = n else: right[i] = stk[-1] stk.append(i) res = 0 for i in range(n): res = max(res, heights[i]*(right[i]-left[i]-1)) return res
42. 接雨水
思路:
- 这道题用栈保存当前最小的高度,当出现一个比栈顶高的高度,则弹出进行这一小部分的计算。
- 整体接雨水的方式就是一小块一小块加起来
class Solution: def trap(self, height: List[int]) -> int: stk = [] res = 0 for i in range(len(height)): last = 0 while stk and height[stk[-1]] <= height[i]: t = stk.pop() res += (i-t-1) * (height[t]-last) last = height[t] if stk: res += (i-stk[-1]-1)*(height[i]-last) stk.append(i) return res
239. 滑动窗口最大值
思路:
- 滑动窗口的最大值主要思路就是保持一个队列,队列中始终保持一个递减的队列。
- 队头始终是当前窗口最大值,队尾始终是当前窗口最小值。
- 当队头超过了窗口范围弹出即可。
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: q, res = [], [] for i in range(len(nums)): if q and i-k>=q[0]: q.pop(0) while q and nums[i]>=nums[q[-1]]: q.pop() q.append(i) if i-k+1>=0: res.append(nums[q[0]]) return res
918. 环形子数组的最大和
思路:
- 这类环形数组题,可以考虑的tips是将其展开为一排,展开为2n的一排,这样就变成了控制一个长度为n的滑动窗口,求窗口内的最大值
- 求前缀和,sum_[i]-sum_[j]就是j+1...i的和,用res记录最大值,时刻更新即可
class Solution: def maxSubarraySumCircular(self, A: List[int]) -> int: n = len(A) for i in range(n): A.append(A[i]) sum_ = [0]*(2*n) for i in range(2*n): sum_[i] = sum_[i-1] + A[i] queue = [0] res = sum_[0] for i in range(1, 2*n): if queue and i - n>queue[0]: queue.pop(0) if queue: res = max(res, sum_[i] - sum_[queue[0]]) while queue and sum_[i] <= sum_[queue[-1]]: queue.pop() queue.append(i) return res
-
单调队列详细图解-leetcode239滑动窗口最大值
2020-08-24 17:12:281. 单调队列(双端队列) 核心思想是维持deque/双端队列中的元素保持递增or递减。...单调栈介绍详见:https://blog.csdn.net/LutherK/article/details/107023543 另外:单调队列还被应用于“多重背包...1. 单调队列(双端队列)
核心思想是维持deque/双端队列中的元素保持递增or递减。
使用该数据结构的优点是deque在队列两端都可以添加、删除元素,这里借助了它其中4种常数时间复杂度的操作(java):offerLast(n)、getFirst()、pollFirst()、pollLast()。
单调栈介绍详见:https://blog.csdn.net/LutherK/article/details/107023543
另外:单调队列还被应用于“多重背包问题”的优化解法。
2. 例题
Leetcode 239题目:
输入: 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
3. 图解
思路:
在一堆数字中,已知最值,如果给这堆数添加一个数,那么比较一下就可以很快算出最值;但如果减少一个数,就不一定能很快得到最值了,而要遍历所有数重新找最值。
首先考虑,要在O(N)的时间内解决此问题,我们需要3个O(1)的操作帮助我们完成,分别是:
push(n):在队列末尾添加元素n;
max:取当前队列/窗口中的最大值;
pop(n):r若队首元素是n,则删除n;
在Java中的实现如下:
// 用于"单调队列"的成员内部类 private static class MonotonicQueue { Deque<Integer> deque = new ArrayDeque<>(); void push(int n){ while(!deque.isEmpty() && deque.getLast()<n) deque.pollLast(); deque.offerLast(n); } // int max(){ return deque.getFirst(); } // void pop(int n){ if(!deque.isEmpty() && deque.getFirst()==n) deque.pollFirst(); } }
4. 完整Java代码
// (2) 双端队列(单调队列) public static int[] maxSlidingWindow2(int[] nums, int k) { int n = nums.length; MonotonicQueue window = new MonotonicQueue(); int[] res = new int[n-k+1]; for(int i=0;i<n;i++){ if(i<k-1) window.push(nums[i]); else { window.push(nums[i]); res[i-k+1] = window.max(); window.pop(nums[i-k+1]); } } return res; } // 用于"单调队列"的成员内部类 private static class MonotonicQueue { Deque<Integer> deque = new ArrayDeque<>(); void push(int n){ while(!deque.isEmpty() && deque.getLast()<n) deque.pollLast(); deque.offerLast(n); } // int max(){ return deque.getFirst(); } // void pop(int n){ if(!deque.isEmpty() && deque.getFirst()==n) deque.pollFirst(); } }
补充:
此题还有另外一种解法,时间复杂度也是O(N),可以说是DP,也可是看做“同步双向遍历”。
代码:
// (1)动态规划 // left[i] 表示从窗口开始到下标i的最大值 // right[j] 表示从窗口末尾到索引j的最大值 public static int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; if (n * k == 0) return new int[0]; if (k == 1) return nums; int[] left = new int[n]; left[0] = nums[0]; int[] right = new int[n]; for (int i = 1; i < n; i++) { if (i%k==0) left[i] = nums[i]; else left[i] = Math.max(left[i-1],nums[i]); int j = n-1-i; if((j+1)%k==0) right[j] = nums[j]; else right[j] = Math.max(right[j+1],nums[j]); } int[] res = new int[n-k+1]; for (int i = 0; i <= n - k; i++) { res[i] = Math.max(right[i],left[i+k-1]); } return res; }
纯属个人见解,如有错误望批评指正!
-
力扣 leetcode 239. 滑动窗口最大值 滑动窗口法结合单调递减栈 (python)
2021-01-03 00:29:48给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 Example 1: 输入:nums = [1...Topic:
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。Example 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] 7Example 2:
输入:nums = [1], k = 1
输出:[1]Example 3:
输入:nums = [1,-1], k = 1
输出:[1,-1]Example 4:
输入:nums = [9,11], k = 2
输出:[11]Example 5:
输入:nums = [4,-2], k = 2
输出:[4]Solution:
一开始的思路其实是将每个窗口的值遍历在栈中
同时每次max栈中的值返回在ans中
但是由于max函数运行效率太低,无法通过运算量过大的样例
所以利用滑动窗口法对思路进行简化避免使用max函数:首先对nums一一遍历,并维持一个单调递减栈
先将第一个值的索引入栈
若后面遍历的值比栈中索引对应的最小的值要小则直接索引入栈
只要后面遍历的值比栈中索引对应的值要大或相等则将最后一个值去除
直到后面遍历的值比栈中索引对应的的值要小则将对应的索引入栈
以此重复维持一个单调递减栈但是由于k(滑动窗口)的长度是一定的
则利用滑动窗口的方法
若最大值的索引小于窗口的左边界(i - k)则将最左侧的值去除
而i就是实时右边界所以无需处理右边界同时当窗口存在(i + 1 > k时):
每一次遍历(移动窗口)将栈中最大值的索引对应的最大值加入ans中Code:
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: a = collections.deque() ans = [] for i in range(len(nums)): while a and nums[a[-1]] <= nums[i]: a.pop() a.append(i) if a[0] <= i - k: a.popleft() if i + 1 >= k: ans.append(nums[a[0]]) return ans
Result:
-
LeetCode 239. 滑动窗口最大值(双端队列+单调栈)
2019-08-14 23:39:16给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 示例: 输入: nums = [1,3,-1,-3,...1. 题目信息
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例: 输入: 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
提示:
你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。
进阶:
你能在线性时间复杂度内解决此题吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。2. 解题
2.1 暴力法
双重循环查找,O(nk)复杂度
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { if(nums.size() == 0) return {}; int maxnum, i, j; vector<int> ans; for(i = 0; i < nums.size()-k+1; ++i) { maxnum = nums[i]; for(j = i+1; j < k+i; ++j) { if(nums[j] > maxnum) maxnum = nums[j]; } ans.push_back(maxnum); } return ans; } };
2.2 双端队列法
将双端队列看做栈,单调递减栈法。
- 在双端队列里保存下标
- 队首保存最大的,队尾保存小的
- 但是注意规则:
- 过了窗口的范围的删除
- 在窗口范围内的k个,每加入一个数nums[i],只保留前面比它大的,<=nums[i] 的没必要存在,该窗口内它是比较大的
对 {1,3,-1,-3,5,3,6,7},k = 3
先建立前k个元素的队列:{1},{1,3},{1,3,-1}(队列变化过程)(为了方便我用元素值表示)
对后面n-k个元素分别操作:
{3,-1,-3}
{-1,-3,5}
{-3,5,3}
{5,3,,6}
{3,6,7}
每次取出队首就是答案。3,3,5,5,6,7
每个元素进出队列,时间复杂度O(n)
class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { if(nums.size() == 0) return {}; deque<int> q; vector<int> ans; int i; for(i = 0; i < k; ++i) { while(!q.empty() && nums[i] >= nums[q.back()]) { q.pop_back();// <=nums[i]的前面的存的,无意义,删掉 } q.push_back(i); } ans.push_back(nums[q.front()]); for(i = k; i < nums.size(); ++i) { if(!q.empty() && i-k+1 > q.front()) q.pop_front();//过了窗口了,删除 while(!q.empty() && nums[i] >= nums[q.back()]) { q.pop_back(); } q.push_back(i); ans.push_back(nums[q.front()]); } return ans; } };
《剑指Offer》面试题59 - I. 滑动窗口的最大值
class Solution { //2020.2.21 public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { if(nums.empty()) return {}; int l = 1, r = 0; vector<int> ans; deque<int> q; while(k--) { while(!q.empty() && nums[q.back()] <= nums[r]) { q.pop_back(); } q.push_back(r++); } ans.push_back(nums[q.front()]); while(r < nums.size()) { if(q.front() < l) q.pop_front(); while(!q.empty() && nums[q.back()] <= nums[r]) { q.pop_back(); } q.push_back(r++); l++; ans.push_back(nums[q.front()]); } return ans; } };
-
leetcode239_滑动窗口最大值
2020-01-27 15:45:571. 运用滑动窗口模板解题, 具体可以看滑动窗口总结这篇. 2. 但是我们需要注意每次类似维护一个单调递减栈,这样front就是最大值,然后移除之后,下一个就是下一个窗口的最大值. 3. 遇到大于back值的,就循环将最大值... -
[LeetCode 困难 单调栈]239. 滑动窗口最大值
2021-02-24 18:10:04给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 示例 1: 输入:nums = [1,3... -
2020-5 leetcode 239. 滑动窗口最大值
2020-05-07 22:55:471.利用单调栈(单调递减)来存储每一次滑动窗口的最大值的下标。注意要实时的判断单调栈的栈底值(最大)是否存在于当前窗口内。 然后根据结果进行值的更新 class Solution { public: vector<int> ... -
数据结构与算法专题汇总(七)队列的leetcode题:滑动窗口最大值,二叉树平均值,栈实现队列,队列实现栈
2020-09-15 22:43:461.滑动窗口最大值 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 解题思路: 用... -
LeetCode 239 Hard 滑动窗口内最大值 Python
2019-01-17 15:10:10def maxSlidingWindow(self, nums, k): ... 和单调栈类似,单调栈是栈内元素保持某种单调性,单调双向队列是队列内保持某种单调性,然后由于本题的背景, 所以使用双向队列 首先要明确➡️单调队列保持队... -
编程集训第3天:队列及堆排序思想--LeetCode滑动窗口的最大值(239)
2018-12-20 19:01:21编程集训第3天:队列及堆排序思想--LeetCode滑动窗口的最大值(239)基础知识编程题目知识回顾 基础知识 一、队列(queue) 队列和栈一样,在实际程序的算法设计和计算机一些其他分支里,都有很多重要的应用,... -
leetcode(六) 滑动窗口、双指针与单调队列/栈
2020-03-08 17:11:19滑动窗口最大值(单调队列) 918.环形子数组的最大和(前缀和+单调队列) 167.两数之和II (双指针) 明显的双指针 做了那么多双指针,其一般的写法都是具有一个从前向后和一个从后向前的指针 因为这样比较容易达成遍历O... -
LeetCode#239,滑动窗口最大值,学习单调队列使用
2020-06-11 15:13:06单调队列 单调队列顾名思义就是队列中元素递增或者递减,...给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。(你 -
【LeetCode系列】双指针、滑动窗口、单调栈、单调对列
2019-11-07 09:35:25专题六:双指针、滑动窗口、单调栈、单调队列 LeetCode 167 两数之和II 1、分析 2、代码 LeetCode 88 合并两个有序数组 1、分析 2、代码 LeetCode 26 删除排序数组中的重复项 1、分析 2、代码 LeetCode 76...
-
成绩文件合并.txt
-
互联网协议 — GRE 通用路由封装协议
-
Nezzar and Lucky Number
-
HP_M1130_M1210_MFP_Full_Solution-v20180815-10158769.rar
-
MySQL 数据库权限管理(用户高级管理和精确访问控制)
-
PowerBI重要外部工具详解
-
SQL漏洞初次认识
-
智慧校园建设方案.ppt
-
物联网基础篇:快速玩转MQTT
-
使用vue搭建微信H5公众号项目
-
Redis 常用数据结构
-
Redis键空间通知(Keyspace Notification)
-
数据作为一种新型生产要素,早已成为推动国经济质量发展的重要动能
-
最新中文停用词.txt
-
Docker从入门到精通
-
【爬虫】糗事百科信息爬取
-
Kubernetes技术分享.pptx
-
MySQL 触发器
-
投标方法论
-
100道MySQL数据库经典面试题解析(有空必看)