更多优质内容
请关注公众号

算法小白的入门日记(三十一)单调栈和单调队列-张柏沛IT博客

正文内容

算法小白的入门日记(三十一)单调栈和单调队列

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-27 19:47 浏览量:212
本系列文章目录
展开/收起

· 单调栈

单调(递增)栈是一个从栈顶到栈底按元素从小到大排序的栈(单调递增栈的元素从栈顶到栈底是从小到大,单调递减栈的元素从栈顶到栈底是从大到小)。

 

单调(递增)栈特点如下

1、从栈顶到栈底的方向,元素是从小到大排序的。

2、元素A入栈时,会先把比A小的元素全部出栈之后才将A入栈。因此每次入栈的元素都会位于栈顶,无论该元素有多大,都会是入栈后,栈内最小的元素。

3、虽然单调栈本身是有序的,但其实它并不能直接用于给一个序列排序。

 

 

 

下面我们看几道和单调栈有关的题目

力扣496. 下一个更大元素 I

给你两个 没有重复元素 的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个(不一定相邻)比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。

 

分析:

本题可以将nums2的所有元素从后往前的放入单调递增栈,假设放入的元素为 A,栈顶元素为B,则A在nums2中的下标肯定比B要前。

若B>A,则B就是A的下一个比A大的元素。此时需将B记录下来作为A的解。

若A>=B,则B是排在A之后的比A小的元素,而A的下一个比A大的元素应该在栈内比B深的地方,此时应该循环出栈直到栈顶比A大。此时需将最新的栈顶记录下来作为A的解。

如果栈空了也找不到比A大的元素,说明A是目前为止最大的元素,此时A的解为-1。

无论A的解是多少,都要将A入栈。

以 [1, 3, 4, 2]为例, 2的解为-1,4的解为为-1,3的解为4,1的解为3。因此解的集合为res = [3, 4, -1,-1]。

但根据题意,我们只需要 nums1 = [4,1,2]的解,而不需要所有的解。因此我们需要在上面入栈的过程中将每一个nums2的value与其对应的key的映射关系记录到一个vkMap哈希表,这样就可以快速得到 nums1[i]的解。

nums1[i]的解为 res[vkMap[nums1[i]]]。

 

import (
   "container/list"
)

func nextGreaterElement(nums1 []int, nums2 []int) []int {
   res2 := make([]int, len(nums2))
   res1 := make([]int, len(nums1))
   vkMap := make(map[int]int)
   stack := list.New()

   for i:=len(nums2)-1; i>=0; i--{
      vkMap[nums2[i]] = i             // 记录答案的下标
      for true {
         if stack.Len() > 0{
            topVal := stack.Back().Value.(int)    // 栈顶的值
            if topVal <= nums2[i]{
               stack.Remove(stack.Back())
               continue
            }
            res2[i] = topVal
         }else{
            res2[i] = -1
         }
         stack.PushBack(nums2[i])      // 入栈
         break
      }
   }

   for i:=0; i<len(nums1); i++{
      res1[i] = res2[vkMap[nums1[i]]]
   }
   return res1
}

 

另一种思路是将nums2的元素从左到右放入到递增单调栈中,假设栈顶元素为A,入栈元素为B,则:

A >= B,不会发生出栈,不记录任何内容;

A < B,说明A的下一个比自己大的元素是B,因此将A出栈,并在hashmap中记录A的解为B。

当nums2遍历结束后,栈中剩下的元素都是解为-1的元素。

 

这种解法和上面解法不同点在于,前者是入栈时记录入栈元素的解,后者是入栈时记录出栈元素的解。

 

# python实现
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []      # 单调递增栈
        hashmap = {}  # 记录单调递增栈中入栈时被弹出元素的解
        res = []

        for n2 in nums2:
            while len(stack) > 0 and n2 > stack[-1]:
                hashmap[stack.pop()] = n2

            stack.append(n2)

        for n1 in nums1:
            res.append(hashmap.get(n1, -1))

        return res

 

只要是使用单调栈的思路,无论使用递增栈还是递减栈,是从左到右遍历nums2还是倒着遍历nums2,都能得出正确结果。

 

本题也可以使用暴力解,nums1=[4,1,2], nums2=[1,3,4,2],我只需要找到nums1[i]在nums2的下标k,并遍历k~len(nums2)-1,从这个范围找下一个比nums1[i]大的值。例如 nums1[0] 为 4, 在nums2的下标是2,就只需要遍历nums[2:]的范围即可。为了快速找到nums1[i]在nums2的位置,可以用hashmap记录下所有num2的value与index的映射关系。

func nextGreaterElement2(nums1 []int, nums2 []int) []int {
   res, vkMap := make([]int, len(nums1)), make(map[int]int)

   for i:=0; i<len(nums2); i++{
      vkMap[nums2[i]] = i
   }

   for i:=0; i<len(nums1); i++{
      idx := vkMap[nums1[i]]    // nums[i]在nums2中的位置
      if idx == len(nums2) - 1{
         res[i] = -1
         continue
      }

      flag := false
      for j:=idx+1; j<len(nums2); j++{
         if nums1[i] < nums2[j]{
            res[i] = nums2[j]
            flag = true
            break
         }
      }
      if !flag{
         res[i] = -1
      }
   }
   return res
}

 

假设nums1长度为M,nums2长度为N,则暴力解时间复杂度O(MN),空间复杂度O(N);单调栈解的时间复杂度O(N+M),空间复杂度O(N)。

 

力扣739. 每日温度

请根据每日 气温 列表 temperatures ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 0 来代替。

这道题和上一题可以说是一模一样,思路和做法可以完全照搬。

代码实现如下:

func dailyTemperatures (temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := list.New()     // 单调栈里面放的是温度的下标
    stack.PushBack(len(temperatures)-1)
    for i:=len(temperatures)-2; i>=0; i--{
        topTempIdx := stack.Back().Value.(int)      // 栈顶温度的下标
        for stack.Len() > 0 && temperatures[topTempIdx] <= temperatures[i]{
            stack.Remove(stack.Back())
            if stack.Len() > 0{
                topTempIdx = stack.Back().Value.(int)
            }
        }
        if stack.Len() == 0{
            res[i] = 0
        }else{
            res[i] = topTempIdx - i         // 下标值之差就是相隔天数
        }
        stack.PushBack(i)       // 入栈
    }
    return res
}

 

 

力扣503. 下一个更大元素 II

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。

分析:

本题其实是第一题的基础上加上环的考点。难点在于如何模拟环,其技巧在于让数组内容翻倍,例如[2,1,2,4,3]。这个数组可以使用[2,1,2,4,3,2,1,2,4,3]模拟。这样3以后的元素有2,1,2,4这4个数。

对于本题,只需要在单调栈中放入2次nums数组即可,第一次不作为,第二次才真正开始搜索下一个数的行为。

下面是代码实现:

func nextGreaterElements(nums []int) []int {
   res := make([]int, len(nums))
   stack := list.New()

   for i:=len(nums)-1;i>=0;i--{
      stack.PushBack(nums[i])
   }

   for i:=len(nums)-1; i>=0; i--{
      for stack.Len() > 0 && nums[i] >= stack.Back().Value.(int){
         stack.Remove(stack.Back())
      }
      if stack.Len() > 0{
         res[i] = stack.Back().Value.(int)
      }else {
         res[i] = -1
      }
      stack.PushBack(nums[i])
   }
   return res
}

 

另一个模拟环的技巧是用下标对数组长度取模,其思维本质上还是让数组长度翻倍或者遍历次数翻倍(i可以大于数组长度),例如arr=[2,1,2, 4,3],我们只需通过 arr[i%len(arr)] 就可以让i在超过数组长度范围的情况下循环重复获取数组元素。

模拟成环:

arr := []int{2,1,4,3}
leng, index := len(arr), 0
for true{
    fmt.Println(arr[index % leng])
    index++
}

 

下面是代码实现

func nextGreaterElements2(nums []int) []int {
   res := make([]int, len(nums))
   stack := list.New()
   n := len(nums)

   for i:=2*n-1; i>=0; i--{
      for stack.Len() > 0 && nums[i%n] >= stack.Back().Value.(int){
         stack.Remove(stack.Back())
      }
      // res的长度只有n,但是res被填充过2*n次,每个下标都被填充过2次
      if stack.Len() > 0{
         res[i%n] = stack.Back().Value.(int)
      }else {
         res[i%n] = -1
      }
      stack.PushBack(nums[i%n])
   }
   return res
}

 

 

· 单调队列

单调(递增)队列是一个从队首到队尾按元素从小到大排序的队列(单调递减队列的元素从队首到队尾是从大到小的)。

 

单调(递增)栈特点如下

1、从队首到队尾的方向,元素是从小到大排序的。

2、元素A从队尾入队时,会先把比A大的元素全部从队尾弹出,直到某个最新队尾元素小于A,才将A入队。

3、出队操作只允许从队首出队,此时出队的元素肯定是最小值。

 

单调队列实现如下:

import "container/list"

// 单调递减队列
type DecreaseList struct {
	list *list.List
}

func InitDecreaseList() *DecreaseList{
	return &DecreaseList{list:list.New()}
}

func (this *DecreaseList) Len() int{
	return this.list.Len()
}

// 从队尾入队
func (this *DecreaseList) Push(val int) {
	for this.Len() > 0 && this.Tail() < val{
		this.list.Remove(this.list.Back())		// 移除队尾元素
	}
	this.list.PushBack(val)		// 入队
}

// 从队首出队
func (this *DecreaseList) Pop() int{
	head := this.Head()
	this.list.Remove(this.list.Front())
	return head
}

func (this *DecreaseList) Head() int{
	return this.list.Front().Value.(int)
}

func (this *DecreaseList) Tail() int{
	return this.list.Back().Value.(int)
}

 

 

力扣239. 滑动窗口最大值

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

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

 

分析:本题的关键在于,当窗口往后移动一格之后,如何以O(1)的时间复杂度快速得到大小为k的窗口内的最大值。

答案是使用一个大小为k的从队首到队尾递减的单调队列,如此一来,每次入队和出队都能保证队首是最大值。窗口每次往后移动一位时,就需要从队首弹出窗口的第一个元素(如果这个元素在入队操作时已经被移出则无需弹出),并将移动后的窗口的最后一个元素入队。

 

python实现

# coding=utf-8

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = deque()     # 单调递减队列,队列不直接存nums的元素,而是存nums的下标,deque是一个双端链表,可以模拟队列和栈
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)

        ans = [nums[q[0]]]
        for i in range(k, n):   # k刚好是窗口的下一个元素
            # 往队尾添加元素
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)

            # 从队首弹出元素
            while q[0] <= i - k:
                q.popleft()
            ans.append(nums[q[0]])

        return ans

 

go实现

func maxSlidingWindow(nums []int, k int) []int {
	queue := InitDecreaseList()
	res := make([]int, len(nums)-k+1)

	// 先将nums的前k个元素入队
	for i:=0; i<k; i++{
		queue.Push(nums[i])
	}

	window := []int{0, k-1}		// 窗口的第一个元素和最后一个元素所位于nums的下标
	for window[1] <= len(nums) - 1{
		res[window[0]] = queue.Head()

		// 窗口往后滑动
		if nums[window[0]] == queue.Head(){
			queue.Pop()
		}
		window[0]++
		window[1]++
		if window[1] < len(nums){
			queue.Push(nums[window[1]])
		}
	}
	return res
}

 




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(三十一)单调栈和单调队列

热门推荐
推荐新闻