题目描述
思路解析动画文字版
记牢这一句:每一轮基于本轮开始的数组同时删,谁的左邻比自己大谁就被删。下面从第一轮开始,一对一对地扫。
初始数组 · 还不是非递减：这是初始数组 5,3,4,4,7,3,6。从左往右看,3 比前面的 5 小,是个下降;7 后面又掉到 3,也是下降。只要还存在这种下降,数组就不是非递减,就得继续删。灰色代表已删除(现在一个都没有),红色代表本轮待删,现在开始第一轮。
第 1 轮开始 · 存活序列 [5, 3, 4, 4, 7, 3, 6]：第 1 轮开始。当前还活着的是 5, 3, 4, 4, 7, 3, 6 这 7 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
比较 5 与 3 · 左邻更大,标记删除 3：看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 3。左邻的值 5 比 3 大,构成下降,所以 3 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
比较 3 与 4 · 左邻不更大,保留 4：看这一对:左边是 3,右边紫色是 4。3 没有比 4 大,这里不是下降,4 本轮保留,不标红。继续看下一对。
比较 4 与 4 · 左邻不更大,保留 4：看这一对:左边是 4,右边紫色是 4。4 没有比 4 大,这里不是下降,4 本轮保留,不标红。继续看下一对。
比较 4 与 7 · 左邻不更大,保留 7：看这一对:左边是 4,右边紫色是 7。4 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
比较 7 与 3 · 左邻更大,标记删除 3：看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 3。左邻的值 7 比 3 大,构成下降,所以 3 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
比较 3 与 6 · 左邻不更大,保留 6：看这一对:左边是 3,右边紫色是 6。3 没有比 6 大,这里不是下降,6 本轮保留,不标红。继续看下一对。
第 1 轮结算 · 同时删掉 2 个：第 1 轮结算:刚才标红的 3, 3 这 2 个数同时被删,一起灰掉。剩下绿色的 5, 4, 4, 7, 6 是本轮的幸存者。已完成 1 轮。再看看它还降不降,降就接着来下一轮。
第 2 轮开始 · 存活序列 [5, 4, 4, 7, 6]：第 2 轮开始。当前还活着的是 5, 4, 4, 7, 6 这 5 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
比较 5 与 4 · 左邻更大,标记删除 4：看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 4。左邻的值 5 比 4 大,构成下降,所以 4 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
比较 4 与 4 · 左邻不更大,保留 4：看这一对:左边是 4,右边紫色是 4。4 没有比 4 大,这里不是下降,4 本轮保留,不标红。继续看下一对。
比较 4 与 7 · 左邻不更大,保留 7：看这一对:左边是 4,右边紫色是 7。4 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
比较 7 与 6 · 左邻更大,标记删除 6：看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 6。左邻的值 7 比 6 大,构成下降,所以 6 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
第 2 轮结算 · 同时删掉 2 个：第 2 轮结算:刚才标红的 4, 6 这 2 个数同时被删,一起灰掉。剩下绿色的 5, 4, 7 是本轮的幸存者。已完成 2 轮。再看看它还降不降,降就接着来下一轮。
第 3 轮开始 · 存活序列 [5, 4, 7]：第 3 轮开始。当前还活着的是 5, 4, 7 这 3 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
比较 5 与 4 · 左邻更大,标记删除 4：看这一对:左边绿色的基准要么是保留的邻居、要么已经标红,右边紫色是 4。左邻的值 5 比 4 大,构成下降,所以 4 这一步要被删,把它标红。注意它标红后并不马上消失,还要继续给它右边的数当比较基准。
比较 4 与 7 · 左邻不更大,保留 7：看这一对:左边是 4,右边紫色是 7。4 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
第 3 轮结算 · 同时删掉 1 个：第 3 轮结算:刚才标红的 4 这 1 个数同时被删,一起灰掉。剩下绿色的 5, 7 是本轮的幸存者。已完成 3 轮。再看看它还降不降,降就接着来下一轮。
第 4 轮开始 · 存活序列 [5, 7]：第 4 轮开始。当前还活着的是 5, 7 这 2 个数(灰色的是前几轮已经删掉的,固定留在原位当占位)。我拿这一轮开始时的这串数,从左往右一对一对地看,谁的左邻比自己大,就把谁标红等着删。
比较 5 与 7 · 左邻不更大,保留 7：看这一对:左边是 5,右边紫色是 7。5 没有比 7 大,这里不是下降,7 本轮保留,不标红。继续看下一对。
本轮无可删 · 数组已非递减,停止：这一轮从头扫到尾,没有任何一对是左大右小,一个红都没标出来。说明剩下的 5, 7 已经是非递减了,操作到此为止。回头数一数,真正发生删除的一共是 3 轮,所以答案就是 3。
边界想清:单个或本来非递减都是 0;严格递减时一轮就能把后面全删光,答案 1。
面试重点:暴力逐轮 O(n 的平方) 会超时、单调栈从右往左把删除时刻算准、答案取 dp 最大值。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def totalSteps(self, nums: List[int]) -> int: stk = [] ans, n = 0, len(nums) dp = [0] * n for i in range(n - 1, -1, -1): while stk and nums[i] > nums[stk[-1]]: dp[i] = max(dp[i] + 1, dp[stk.pop()]) stk.append(i) return max(dp)复杂度
- 时间：O(n)，单调栈解法里每个下标只入栈一次、出栈一次,遍历一遍即得答案。动画演示的逐轮删除是理解用的暴力法,最坏要 O(n) 轮、每轮 O(n),是 O(n 的平方),数据大时会超时,所以正解用单调栈
- 空间：O(n)，按峰值算。一个下标栈最坏装下接近 n 个元素(整个数组从左到右非递减、递增时,右往左遍历时前面的小数吃不掉更大的栈顶,于是全留在栈里),再加一个长度 n 的 dp 数组,合起来是 O(n)
易错点
面试追问把动画讲成自己的话
追问最直接的暴力怎么做,为什么会超时?
追问单调栈解法为什么从右往左遍历?
追问答案到底取的是什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
螺旋矩阵 IV
LeetCode 2326 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题