更多优质内容
请关注公众号
请关注公众号
· 单调栈
单调（递增）栈是一个从栈顶到栈底按元素从小到大排序的栈（单调递增栈的元素从栈顶到栈底是从小到大，单调递减栈的元素从栈顶到栈底是从大到小）。
单调（递增）栈特点如下
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
}
