后端技术栈_八股文_思维导图_面试

package 滑动窗口 import "math" /* 给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧.你只可以看到在滑动窗口内的 k个数字.滑动窗口每次只向右移动一位.返回滑动窗口中的最大值. */ func maxSlidingWindow(nums []int, k int) []int { /* 滑动窗口中的最大值: 当滑动窗口移动时候,改变的元素只有窗口左边界的元素和窗口右边界的元素 假设被排除在外的左边界元素为left,被移入的左边界元素为right,上一个滑动窗口的最大值为maxRes 1. 如果 right>=maxRes:则maxRes=right,则继续移动 否则: if left==maxRes ,则说明left是上一个滑动窗口的最大值则重新计算窗口内的最大值 */ maxRes:=math.MinInt res:=make([]int,0) for i:=0;i<len(nums)&&i<k;i++{ maxRes=max(maxRes,nums[i]) } res=append(res,maxRes) if len(nums)<k{ return res } //如果数组的长度比滑动窗口的长度还要小 left,right:=0,k-1 //左闭右闭区间 for right+1<len(nums){ if nums[right+1]>=maxRes{ maxRes=nums[right+1] }else{ if nums[left]==maxRes{ //则说明可能把最大值移除去了 tmpRes:=math.MinInt for j:=left+1;j<=right+1;j++{//计算[left+1,right+1]中的值 tmpRes=max(tmpRes,nums[j]) } maxRes=tmpRes } } res=append(res,maxRes) //记录下一个滑动窗口的最大值 right++ left++ } return res } //以上的方法超时了,那么可以优化的地方在于33步即如何设计一个数据结构使得当left最大值移除后还能记录下一个最大值 /* 那么就要用空间开销换取时间优化. 利用双端队列=> 双端队列中的下标值性质:从小到大排序且下标值对应的nums值是严格单调递减的 =>进一步表示双端队列中队头元素存放的是当前滑动窗口中的最大值. 举个例子:当双端队列中的队头元素为i,此时滑动窗口的左边界为left(left<i)=>则nums[left,i]之间的最大元素就是nums[i] */ func maxSlidingWindow2(nums []int, k int) []int { /* 自定义一个push操作: 当加入的一个nums[i]>=nums[q[len(q)-1]]时要弹出队尾元素,知道队尾元素比nums[i]大或者队列长度为0时将nums[i]加入队尾 Step1: 初始化双端队列 Step2: 在实际移动滑动窗口前,需要先对队尾元素加入双端队列中,然后判断队头元素if q[0]==left时,表示当前滑动窗口的最大值被移除,那么下一个元素就是下一个滑动窗口的最大值 */ q:=make([]int,0) push:=func (i int){ //把元素加入队列q中 for len(q)>0&&nums[i]>=nums[q[len(q)-1]]{ q=q[:len(q)-1] //删除队尾元素 } q=append(q,i) } //初始化双端队列 for i:=0;i<k;i++{ push(i) } res:=make([]int,0) res=append(res,nums[q[0]]) left,right:=0,k-1//[left,right] for right+1<len(nums){ //开始计算下一个滑动窗口的最大值 push(right+1) if left==q[0]{ q=q[1:] } res=append(res,nums[q[0]]) right++ left++ } return res }