服务好的赣州网站建设,郴州市高中阶段招生录取系统,沈阳做网站 0诚金网络专业,360官网文章目录一、 堆栈基础知识1.1 简介1.2 堆栈的顺序存储1.2.1 堆栈顺序存储基本描述1.2.2 堆栈顺序存储实现代码1.3 堆栈的链式存储1.3.1 堆栈的链式存储基本描述1.3.2 堆栈的链式存储实现代码二、 堆栈的基础应用2.1 堆栈基础题列表2.2 括号匹配问题2.2.1 有效的括号2.2.2 最长…
文章目录一、 堆栈基础知识1.1 简介1.2 堆栈的顺序存储1.2.1 堆栈顺序存储基本描述1.2.2 堆栈顺序存储实现代码1.3 堆栈的链式存储1.3.1 堆栈的链式存储基本描述1.3.2 堆栈的链式存储实现代码二、 堆栈的基础应用2.1 堆栈基础题列表2.2 括号匹配问题2.2.1 有效的括号2.2.2 最长有效括号2.3 前缀、中缀、后缀表达式2.3.1 表达式简介2.3.2 表达式转换原理2.3.3 中缀转后缀算法2.3.4 后缀表达式求值2.4 表达式求值问题2.4.1 基本计算器II2.4.2 逆波兰表达式求值2.4.3 基本计算器I2.5 验证栈序列三、单调栈3.1 单调递增栈3.2 单调递减栈3.3 单调栈适用场景3.3.1 寻找左侧第一个比当前元素大的元素3.3.2 寻找左侧第一个比当前元素小的元素3.3.3 寻找右侧第一个比当前元素大的元素3.3.4 寻找右侧第一个比当前元素小的元素四、 单调栈的应用4.1 单调栈题目列表4.2 下一个更大元素 I II4.3 每日温度4.4 股票价格跨度4.5 去除重复字母4.6 柱状图中最大的矩形4.7 接雨水4.8 最大矩形本文主要参考《算法通关手册》堆栈篇 一、 堆栈基础知识
1.1 简介
堆栈Stack简称为栈。一种线性表数据结构是一种只允许在表的一端进行插入和删除操作的线性表。 我们把栈中允许插入和删除的一端称为 「栈顶top」另一端则称为 「栈底bottom」。当表中没有任何数据元素时称之为 「空栈」。
堆栈有两种基本操作「插入操作」 和 「删除操作」。
栈的插入操作又称为「入栈」或者「进栈」。栈的删除操作又称为「出栈」或者「退栈」。 简单来说栈是一种 「后进先出Last In First Out」 的线性表简称为 「LIFO 结构」。我们可以从两个方面来解释一下栈的定义 「线性表」栈首先是一个线性表栈中元素具有前驱后继的线性关系。栈中元素按照 a1,a2,...,ana_1, a_2, ... , a_na1,a2,...,an 的次序依次进栈。栈顶元素为 ana_nan。 「后进先出原则」根据堆栈的定义每次删除的总是堆栈中当前的栈顶元素即最后进入堆栈的元素。而在进栈时最先进入堆栈的元素一定在栈底最后进入堆栈的元素一定在栈顶。也就是说元素进入堆栈或者退出退栈是按照「后进先出Last In First Out」的原则进行的。
堆栈的基本操作 栈作为一种线性表来说理论上应该具备线性表所有的操作特性但由于「后进先出」的特殊性所以针对栈的操作进行了一些变化。尤其是插入操作和删除操作改为了入栈push和出栈pop。
堆栈的基本操作如下 初始化空栈创建一个空栈定义栈的大小 size以及栈顶元素指针 top。 判断栈是否为空当堆栈为空时返回 True。当堆栈不为空时返回 False。一般只用于栈中删除操作和获取当前栈顶元素操作中。 判断栈是否已满当堆栈已满时返回 True当堆栈未满时返回 False。一般只用于顺序栈中插入元素和获取当前栈顶元素操作中。 插入元素进栈、入栈相当于在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针 top 的指向位置。 删除元素出栈、退栈相当于在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针 top 的指向位置。 获取栈顶元素相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是该操作并不改变栈顶指针 top 的指向位置。
接下来我们来看一下栈的顺序存储与链式存储两种不同的实现方式。
1.2 堆栈的顺序存储
和线性表类似栈有两种存储表示方法「顺序栈」 和 「链式栈」。
「顺序栈」即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素同时使用指针 top 指示栈顶元素在顺序栈中的位置。「链式栈」即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前并使用栈顶指针 top 指示栈顶元素top 永远指向链表的头节点位置。 堆栈最简单的实现方式就是借助于一个数组来描述堆栈的顺序存储结构。在 Python 中我们可以借助列表 list 来实现。这种采用顺序存储结构的堆栈也被称为 「顺序栈」。
1.2.1 堆栈顺序存储基本描述 我们约定 self.top 指向栈顶元素所在位置。
初始化空栈使用列表创建一个空栈定义栈的大小 self.size并令栈顶元素指针 self.top 指向 -1即 self.top -1。判断栈是否为空当 self.top -1 时说明堆栈为空返回 True否则返回 False。判断栈是否已满当 self.top self.size - 1说明堆栈已满返回 True否则返回返回 False。插入元素进栈、入栈先判断堆栈是否已满已满直接抛出异常。如果堆栈未满则在 self.stack 末尾插入新的数据元素并令 self.top 向右移动 1 位。删除元素出栈、退栈先判断堆栈是否为空为空直接抛出异常。如果堆栈不为空则删除 self.stack 末尾的数据元素并令 self.top 向左移动 1 位。获取栈顶元素先判断堆栈是否为空为空直接抛出异常。不为空则返回 self.top 指向的栈顶元素即 self.stack[self.top]。
1.2.2 堆栈顺序存储实现代码
class Stack:# 初始化空栈def __init__(self, size100):self.stack []self.size sizeself.top -1 # 判断栈是否为空def is_empty(self):return self.top -1# 判断栈是否已满def is_full(self):return self.top 1 self.size# 入栈操作def push(self, value):if self.is_full():raise Exception(Stack is full)else:self.stack.append(value)self.top 1# 出栈操作def pop(self):if self.is_empty():raise Exception(Stack is empty)else:self.stack.pop()self.top - 1# 获取栈顶元素def peek(self):if self.is_empty():raise Exception(Stack is empty)else:return self.stack[self.top]1.3 堆栈的链式存储 堆栈的顺序存储结构保留着顺序存储分配空间的固有缺陷即在栈满或者其他需要重新调整存储空间时需要移动大量元素。为此堆栈可以采用链式存储方式来实现。在 Python 中我们通过构造链表节点 Node 的方式来实现。这种采用链式存储结构的堆栈也被称为 「链式栈」。 1.3.1 堆栈的链式存储基本描述
我们约定 self.top 指向栈顶元素所在位置。
初始化空栈使用列表创建一个空栈并令栈顶元素指针 self.top 指向 None即 self.top None。判断栈是否为空当 self.top None 时说明堆栈为空返回 True否则返回 False。插入元素进栈、入栈创建值为 value 的链表节点插入到链表头节点之前并令栈顶指针 self.top 指向新的头节点。删除元素出栈、退栈先判断堆栈是否为空为空直接抛出异常。如果堆栈不为空则先使用变量 cur 存储当前栈顶指针 self.top 指向的头节点然后令 self.top 沿着链表移动 1 位然后再删除之前保存的 cur 节点。获取栈顶元素先判断堆栈是否为空为空直接抛出异常。不为空则返回 self.top 指向的栈顶节点的值即 self.top.value。
1.3.2 堆栈的链式存储实现代码
class Node:def __init__(self, value):self.value valueself.next Noneclass Stack:# 初始化空栈def __init__(self):self.top None# 判断栈是否为空def is_empty(self):return self.top None# 入栈操作def push(self, value):cur Node(value)cur.next self.topself.top cur# 出栈操作def pop(self):if self.is_empty():raise Exception(Stack is empty)else:cur self.topself.top self.top.nextdel cur# 获取栈顶元素def peek(self):if self.is_empty():raise Exception(Stack is empty)else:return self.top.value二、 堆栈的基础应用
堆栈是算法和程序中最常用的辅助结构其的应用十分广泛。堆栈基本应用于两个方面
使用堆栈可以很方便的保存和取用信息因此长被用作算法和程序中的辅助存储结构临时保存信息供后面操作中使用。 例如操作系统中的函数调用栈浏览器中的前进、后退功能。 堆栈的后进先出规则可以保证特定的存取顺序。 例如翻转一组元素的顺序、铁路列车车辆调度。
2.1 堆栈基础题列表
题号标题题解标签难度1047删除字符串中的所有相邻重复项Python字符串、栈简单0155最小栈Python栈、设计简单0020有效的括号Python栈、字符串简单0227基本计算器 IIPython栈、字符串中等0739每日温度Python栈、哈希表中等0150逆波兰表达式求值Python栈中等0232用栈实现队列Python栈、设计简单剑指 Offer 09用两个栈实现队列Python栈、设计、队列简单0394字符串解码Python栈、深度优先搜索中等0032最长有效括号Python栈、字符串、动态规划困难0946验证栈序列Python栈、数组、模拟中等剑指 Offer 06从尾到头打印链表Python栈、递归、链表、双指针简单0739每日温度Python栈、哈希表中等0071简化路径
下面我们来讲解一下栈应用的典型例子。
2.2 括号匹配问题
2.2.1 有效的括号 20. 有效的括号 - 力扣LeetCode 给定一个只包括 (){}[] 的字符串 s 判断字符串 s 是否有效即括号是否匹配。
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例
输入s “()[]{}”输出True
解题思路括号匹配是「栈」的经典应用。我们可以用栈来解决这道题。
先判断一下字符串的长度是否为偶数。因为括号是成对出现的所以字符串的长度应为偶数可以直接判断长度为奇数的字符串不匹配。如果字符串长度为奇数则说明字符串 s 中的括号不匹配直接返回 False。使用栈 stack 来保存未匹配的左括号。然后依次遍历字符串 s 中的每一个字符。 如果遍历到左括号时将其入栈。如果遍历到右括号时先看栈顶元素是否是与当前右括号相同类型的左括号。 如果是与当前右括号相同类型的左括号则令其出栈继续向前遍历。如果不是与当前右括号相同类型的左括号则说明字符串 s 中的括号不匹配直接返回 False。 遍历完还要再判断一下栈是否为空。 如果栈为空则说明字符串 s 中的括号匹配返回 True。如果栈不为空则说明字符串 s 中的括号不匹配返回 False。
代码
class Solution:def isValid(self, s: str) - bool:if len(s) % 2 1:return Falsestack list()for ch in s:if ch ( or ch [ or ch {:stack.append(ch)elif ch ):if len(stack) !0 and stack[-1] (:stack.pop()else:return Falseelif ch ]:if len(stack) !0 and stack[-1] [:stack.pop()else:return Falseelif ch }:if len(stack) !0 and stack[-1] {:stack.pop()else:return Falseif len(stack) 0:return Trueelse:return False时间复杂度O(n)O(n)O(n)。空间复杂度O(1)O(1)O(1)。
2.2.2 最长有效括号 32 最长有效括号 - 力扣LeetCode 给你一个只包含 ‘(’ 和 ‘)’ 的字符串找出最长有效格式正确且连续括号子串的长度。 示例
输入s “)()())”输出4解释最长有效括号子串是 “()()”
参考官方题解使用单调栈来解决。主要思路是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」。
对于遇到的每个 ‘(’ 直接入栈对于遇到的每个 ‘)’ 我们先弹出栈顶元素表示匹配了当前右括号 如果栈为空说明当前的右括号为没有被匹配的右括号我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 如果栈不为空当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」。 我们从前往后遍历字符串并更新答案即可。 注意如果一开始栈为空第一个字符为左括号的时候我们会将其放入栈中这样就不满足提及的「最后一个没有被匹配的右括号的下标」为了保持统一我们在一开始的时候往栈中放入一个值为 −1 的元素。 class Solution:def longestValidParentheses(self, s: str) - int:stack[-1] # 初始赋值为-1这样匹配到都一个右括号时长度1--12刚刚好。ans0for i in range(len(s)):if s[i](:stack.append(i)else:stack.pop()if len(stack)0:stack.append(i)else:ansmax(ans,i-stack[-1]) return ans时间复杂度O(n)O(n)O(n)。空间复杂度O(n)O(n)O(n)。
2.3 前缀、中缀、后缀表达式
2.3.1 表达式简介
中缀表达式 中缀表达式操作符介于操作数之间的表达式。中缀(infix)表达式A B * C D 为了避免计算顺序混淆引入全括号表达式全括号中缀表达式((A (B * C)) D)内层括号优先级更高。 前缀和后缀表达式 前缀(prefix)表达式将操作符移到前面形式变为操作符、第一操作数、第二操作数。后缀(postfix)表达式将操作符移到后面形式变为第一操作数、第二操作数、操作符。 2.3.2 表达式转换原理
例(A (B * C))
中缀转后缀表达式把操作符移到相应的右括号替代之并删掉左括号 把操作符*移到子表达式(B * C)的右括号位置替代它再删去左括号得到BC*把操作符移到相应的右括号并删掉左括号表达式就转为 后缀 形式即ABC* 。 中缀转前缀表达式同理把操作符移到相应的左括号替代之并删掉右括号表达时就转换为 前缀 形式即A*BC 。
总结
前后缀表达式中操作符顺序完全决定了运算的次序多数情况下计算机用此方法特别是后缀法。离操作数越近的越先做无论表达式多复杂转换为前缀或后缀只需要两个步骤 将中缀表达式转换为全括号形式将所有操作符移动到子表达式所在的左括号前缀或者右括号后缀处替代之再删除所有括号。
2.3.3 中缀转后缀算法
在中缀表达式转换为后缀形式的处理过程中操作符比操作数要晚输出所以在扫描到对应的第二个操作数之前需要把操作符先保存起来而这些暂存的操作符由于优先级的规则还有可能要反转次序输出。 在AB*C中虽然先出现但优先级比后面这个*要低所以它要等*处理完后才能再处理。这种反转特性使得我们考虑用栈来保存暂时未处理的操作符。 总结下在从左到右扫描逐个字符扫描中缀表达式的过程中采用一个栈来暂存未处理的操作符。这样栈顶的操作符就是最近暂存进去的当遇到一个新的操作符就需要跟栈顶的操作符比较下优先级再行处理。 所以遇到左括号要标记下其后出现的操作符优先级提升了一旦扫描到对应的右括号就可以马上输出这个操作符
流程
从左到右扫描中缀表达式单词列表 如果单词是操作数则直接添加到后缀表达式列表的末尾如果单词是左括号则压入opstack栈顶如果单词是右括号则反复弹出opstack栈顶操作符加入到输出列表末尾直到碰到左括号如果单词是操作符则压入opstack栈顶但在压入栈顶之前要比较其与栈顶操作符的优先级如果栈顶的高于或等于它就要反复弹出栈顶操作符加入到输出列表末尾直到栈顶的操作符优先级低于它。 中缀表达式单词列表扫描结束后把opstack栈中的所有剩余操作符 依次弹出添加到输出列表末尾。把输出列表再用join方法合并成后缀表达式字符串算法结束。
代码实现
from pythonds.basic.stack import Stackdef infixToPostfix(infixexpr):prec {}prec[*] 3prec[/] 3prec[] 2prec[-] 2prec[(] 1opStack Stack()postfixList []tokenList infixexpr.split()for token in tokenList:if token in ABCDEFGHIJKLMNOPQRSTUVWXYZ or token in 0123456789:postfixList.append(token)elif token (:opStack.push(token)elif token ):topToken opStack.pop()while topToken ! (:postfixList.append(topToken)topToken opStack.pop()else:while (not opStack.isEmpty()) and \(prec[opStack.peek()] prec[token]):postfixList.append(opStack.pop())opStack.push(token)while not opStack.isEmpty():postfixList.append(opStack.pop())return .join(postfixList)2.3.4 后缀表达式求值
创建空栈operandStack用于暂存操作数。将后缀表达式用split方法解析为单词token的列表。从左到右扫描单词列表如果单词是一个操作数将单词转换为整数int压入operandStack栈顶如果单词是一个操作符就开始求值从栈顶弹出两个操作数先弹出的是右操作数后弹出的是左操作数计算后将值重新压入栈顶。单词列表扫描结束后表达式的值就在栈顶。弹出栈顶的值返回。 代码实现
from pythonds.basic.stack import Stackdef postfixEval(postfixExpr):operandStack Stack()tokenList postfixExpr.split()for token in tokenList:if token in 0123456789:operandStack.push(int(token))else:operand2 operandStack.pop()operand1 operandStack.pop()result doMath(token,operand1,operand2)operandStack.push(result)return operandStack.pop()def doMath(op,op1,op2):if op *:return op1 * op2elif op /:return op1 / op2elif op :return op1 op2else:return op1 - op22.4 表达式求值问题
2.4.1 基本计算器II 227. 基本计算器 II - 力扣LeetCode 给定一个字符串表达式 s表达式中所有整数为非负整数运算符只有 、-、*、/没有括号。请实现一个基本计算器来计算并返回它的值。
1≤s.length≤3∗1051 \le s.length \le 3 * 10^51≤s.length≤3∗105。s 由整数和算符、-、*、/组成中间由一些空格隔开。s 表示一个有效表达式。表达式中的所有整数都是非负整数且在范围 [0,231−1][0, 2^{31} - 1][0,231−1] 内。题目数据保证答案是一个 32-bit 整数。
示例
输入s “32*2”输出7
解题思路 计算表达式中乘除运算优先于加减运算。我们可以先做所有的乘除运算将其结果放回表达式的原位置这样整个表达式的值就成了一系列加减的结果。
遍历字符串使用op记录每个数字之前的运算符。对于第一个数字其之前的运算符视为‘’。每次遍历到数字末尾时根据op决定当前数字的计算方式直接入栈-将数字的负数入栈*/将栈顶数字弹出计算其与当前数字的结果再将计算结果入栈处理完当前数字后更新操作符op进行下一次计算遍历完后计算栈中所有数字的累加结果
class Solution:def calculate(self, s: str) - int:slist(s)stack[]op # 记录操作符默认为numfor i in range(len(s)):if s[i].isdigit():nums[i]if ilen(s)-1 or s[i] in -*/:numint(num)if op:stack.append(num)elif op-:stack.append(-num)elif op*:stack.append(stack.pop()*num)elif op/:stack.append(int(stack.pop()/num))ops[i]numreturn sum(stack)2.4.2 逆波兰表达式求值 150. 逆波兰表达式求值 给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。
两个整数之间的除法总是 向零截断表达式中不含除零运算输入是一个根据逆波兰表示法表示的算术表达式有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。示例 输入tokens [10,6,9,3,,-11,*,/,*,17,,5,]输出22该算式转化为常见的中缀算术表达式为 ((10 * (6 / ((9 3) * -11))) 17) 5 本题实际是后缀表达式求值问题。因为前缀或者后缀表达式中靠近数字的操作符先运算所以不存在中缀表达式那种需要先比较运算符优先级的情况直接运算就行了。唯一注意的是数字可以是负数需要稍微处理一下。
class Solution:def evalRPN(self, tokens: List[str]) - int:Stack [] for token in tokens:# 数字直接入栈负数将其乘以-1再入栈if token.isdigit():Stack.append(int(token))elif token[0]- and len(token)1:# 此时表示的是负数Stack.append(int(token[1:])*-1)# 碰到操作符就开始运算弹出的第一个栈顶元素是第二操作数 else: num2 Stack.pop()num1 Stack.pop()result self.doMath(token,num1,num2)Stack.append(result)return Stack.pop()def doMath(self,op,num1,num2):if op *:return num1 * num2elif op /:return int(num1 / num2)elif op :return num1 num2else:return num1 - num22.4.3 基本计算器I 224. 基本计算器 给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。
s 由数字、加减乘除和小括号 组成‘’ 不能用作一元运算例如 “1” 和 “(2 3)” 无效‘-’ 可以用作一元运算即 “-1” 和 “-(2 3)” 是有效的输入中不存在两个连续的操作符示例 输入 s (1(452)-3)(68)输出23
解题思路一括号展开栈
class Solution:def calculate(self, s: str) - int:ops [1]sign 1ret 0n len(s)i 0while i n:if s[i] :i 1elif s[i] :sign ops[-1]i 1elif s[i] -:sign -ops[-1]i 1elif s[i] (:ops.append(sign)i 1elif s[i] ):ops.pop()i 1else:num 0while i n and s[i].isdigit():num num * 10 ord(s[i]) - ord(0)i 1ret num * signreturn ret解题思路2构造nums和ops两个栈分别存放操作数和操作符然后遍历表达式 参考《使用「双栈」解决「究极表达式计算」问题》 遇到空格跳过遇到数字将连续数字直接在nums中入栈负数乘以-1遇到右括号时优先级最大反复弹出ops和nums中的元素进行计算直到遇到左括号将结果存入nums中。因为我们是从前往后做的假设我们当前已经扫描到 2 1 了此时栈内的操作为 。遇到操作符在ops中入栈。在放入之前先把栈内可以算的都算掉只有「栈内运算符」比「当前运算符」优先级高/同等才进行运算使用现有的 nums 和 ops 进行计算直到没有操作或者遇到左括号计算结果放到 nums 以2 1为例如果后面出现的 2 或者 - 1 的话满足「栈内运算符」比「当前运算符」优先级高/同等可以将 2 1 算掉把结果放到 nums 中如果后面出现的是 * 2 或者 / 1 的话不满足「栈内运算符」比「当前运算符」优先级高/同等这时候不能计算 2 1。由于第一个数可能是负数为了减少边界判断。一个小技巧是先往 nums 添加一个 0为防止 () 内出现的首个字符为运算符将所有的空格去掉并将 (- 替换为 (0-( 替换为 (0当然也可以不进行这样的预处理将这个处理逻辑放到循环里去做
2.5 验证栈序列 946 验证栈序列 给定 pushed 和 popped 两个序列每个序列中的 值都不重复只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时返回 true否则返回 false 。
示例 1 输入pushed [1,2,3,4,5], popped [4,5,3,2,1]输出true解释我们可以按以下顺序执行 push(1), push(2), push(3), push(4), pop() - 4,push(5), pop() - 5, pop() - 3, pop() - 2, pop() - 1 示例 2 输入pushed [1,2,3,4,5], popped [4,3,5,1,2]输出false解释1 不能在 2 之前弹出。
使用分离双指针i和j分别遍历pushed 和 popped两个数组。再用空栈存储每次操作的元素。
pushed[i]入栈i右移当popped[j]在栈中时开始弹出弹出前进行比较 popped[j]等于栈顶元素时栈顶元素出栈j右移否则弹出次序不对返回False
class Solution:def validateStackSequences(self, pushed: List[int], popped: List[int]) - bool:nlen(popped)stack[]i,j0,0# 分离双指针while in and jn:stack.append(pushed[i])i1while stack and popped[j] in stack:if popped[j]stack[-1]:j1stack.pop()else:return Falsereturn True也可以写成popped[j]等于栈顶元素就出栈遍历完看栈是否为空
class Solution:def validateStackSequences(self, pushed: List[int], popped: List[int]) - bool:nlen(popped)stack[]i,j0,0# 分离双指针while in and jn:stack.append(pushed[i])i1while stack and popped[j]stack[-1]:j1stack.pop() return len(stack)0 三、单调栈 单调栈Monotone Stack一种特殊的栈。在栈的「先进后出」规则基础上要求「从 栈顶 到 栈底 的元素是单调递增或者单调递减」。 单调递增栈从栈顶到栈底的元素是单调递增的栈 单调递减栈从栈顶到栈底的元素是单调递减的栈 注意这里定义的顺序是从「栈顶」到「栈底」。有的文章里是反过来的。本文全文以「栈顶」到「栈底」的顺序为基准来描述单调栈。 3.1 单调递增栈 只有比栈顶元素小的元素才能直接进栈否则需要先将栈中比当前元素小的元素出栈再将当前元素入栈。 下面我们以数组 [2, 7, 5, 4, 6, 3, 4, 2] 为例从左到右遍历模拟一下「单调递增栈」的进栈、出栈过程
第 i 步待插入元素操 作结 果左侧为栈底作 用122 入栈[2]元素 2 的左侧无比 2 大的元素272 出栈7 入栈[7]元素 7 的左侧无比 7 大的元素355 入栈[7, 5]元素 5 的左侧第一个比 5 大的元素为7444 入栈[7, 5, 4]元素 4 的左侧第一个比 4 大的元素为5564 出栈5 出栈6 入栈[7, 6]元素 6 的左侧第一个比 6 大的元素为7633 入栈[7, 6, 3]元素 3 的左侧第一个比 3 大的元素为6743 出栈4 入栈[7, 6, 4]元素 4 的左侧第一个比 4 大的元素为6822 入栈[7, 6, 4, 2]元素 2 的左侧第一个比 2 大的元素为4最终栈中元素为 [7, 6, 4, 2]。因为从栈顶右端到栈底左侧元素的顺序为 2, 4, 6, 7满足递增关系所以这是一个单调递增栈。 我们以上述过程第 5 步为例所对应的图示过程为 以从左到右遍历元素为例单调递增栈伪代码为
def monotoneIncreasingStack(nums):stack []for num in nums:while stack and num stack[-1]:stack.pop()stack.append(num)3.2 单调递减栈 只有比栈顶元素大的元素才能直接进栈否则需要先将栈中比当前元素大的元素出栈再将当前元素入栈。下面我们以数组 [4, 3, 2, 5, 7, 4, 6, 8] 为例模拟一下「单调递减栈」的进栈、出栈过程
第 i 步待插入元素操 作结 果左侧为栈底作用144 入栈[4]元素 4 的左侧无比 4 小的元素234 出栈3 入栈[3]元素 3 的左侧无比 3 小的元素323 出栈2 入栈[2]元素 2 的左侧无比 2 小的元素455 入栈[2, 5]元素 5 的左侧第一个比 5 小的元素是2577 入栈[2, 5, 7]元素 7 的左侧第一个比 7 小的元素是5647 出栈5 出栈4 入栈[2, 4]元素 4 的左侧第一个比 4 小的元素是2766 入栈[2, 4, 6]元素 6 的左侧第一个比 6 小的元素是4888 入栈[2, 4, 6, 8]元素 8 的左侧第一个比 8 小的元素是6最终栈中元素为 [2, 4, 6, 8]。因为从栈顶右端到栈底左侧元素的顺序为 8, 6, 4, 2满足递减关系所以这是一个单调递减栈。 我们以上述过程第 6 步为例所对应的图示过程为 以从左到右遍历元素为例单调递减栈伪代码为
def monotoneDecreasingStack(nums):stack []for num in nums:while stack and num stack[-1]:stack.pop()stack.append(num)3.3 单调栈适用场景
单调栈可以在时间复杂度为 O(n)O(n)O(n) 的情况下求解出某个元素左边或者右边第一个比它大或者小的元素。
所以单调栈一般用于解决一下几种问题
寻找左侧第一个比当前元素大的元素。寻找左侧第一个比当前元素小的元素。寻找右侧第一个比当前元素大的元素。寻找右侧第一个比当前元素小的元素。
下面分别说一下这几种问题的求解方法。
3.3.1 寻找左侧第一个比当前元素大的元素
从左到右遍历元素构造单调递增栈从栈顶到栈底递增 一个元素左侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。如果插入时的栈为空则说明左侧不存在比当前元素大的元素。
3.3.2 寻找左侧第一个比当前元素小的元素
从左到右遍历元素构造单调递减栈从栈顶到栈底递减 一个元素左侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。如果插入时的栈为空则说明左侧不存在比当前元素小的元素。
3.3.3 寻找右侧第一个比当前元素大的元素 从左到右遍历元素构造单调递增栈从栈顶到栈底递增 一个元素右侧第一个比它大的元素就是将其「弹出单调递增栈」时即将插入的元素。如果该元素没有被弹出栈则说明右侧不存在比当前元素大的元素。 从右到左遍历元素构造单调递增栈从栈顶到栈底递增 一个元素右侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。如果插入时的栈为空则说明右侧不存在比当前元素大的元素。
3.3.4 寻找右侧第一个比当前元素小的元素 从左到右遍历元素构造单调递减栈从栈顶到栈底递减 一个元素右侧第一个比它小的元素就是将其「弹出单调递减栈」时即将插入的元素。如果该元素没有被弹出栈则说明右侧不存在比当前元素小的元素。 从右到左遍历元素构造单调递减栈从栈顶到栈底递减 一个元素右侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。如果插入时的栈为空则说明右侧不存在比当前元素小的元素。
上边的分类解法有点绕口可以简单记为以下条规则 无论哪种题型都建议从左到右遍历元素。 查找 「比当前元素大的元素」 就用 单调递增栈查找 「比当前元素小的元素」 就用 单调递减栈。 从 「左侧」 查找就看 「插入栈」 时的栈顶元素从 「右侧」 查找就看 「弹出栈」 时即将插入的元素。
四、 单调栈的应用
4.1 单调栈题目列表
题号标题题解标签难度0739每日温度Python栈、哈希表中等0496下一个更大元素 IPython栈、数组、哈希表、单调栈简单0503下一个更大元素 IIPython栈、数组、单调栈中等0901股票价格跨度Python栈、设计、数据流、单调栈中等0084柱状图中最大的矩形Python栈、数组、单调栈困难0316去除重复字母Python栈、贪心、字符串、单调栈中等1081不同字符的最小子序列Python栈、贪心、字符串、单调栈中等0042接雨水Python栈、数组、双指针、动态规划、单调栈困难0085最大矩形单调栈困难
下面介绍一下经典题目
4.2 下一个更大元素 I II 0496. 下一个更大元素 I0503. 下一个更大元素 II 给定两个没有重复元素的数组 nums1 和 nums2 其中 nums1 是 nums2 的子集。要求找出 nums1 中每个元素在 nums2 中的下一个比其大的值如果不存在对应位置输出 -1。 示例
输入nums1 [4,1,2], nums2 [1,3,4,2].输出[-1,3,-1]解释nums1 中每个值的下一个更大元素如下所述 4 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。1 用加粗斜体标识nums2 [1,3,4,2]。下一个更大元素是 3 。2 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。
解题思路 暴力求解 根据题意直接暴力求解。遍历 nums1 中的每一个元素。对于 nums1 的每一个元素 nums1[i]再遍历一遍 nums2查找 nums2 中对应位置右边第一个比 nums1[i] 大的元素。这种解法的时间复杂度是 O(n2)O(n^2)O(n2)。 使用单调递增栈。因为 nums1 是 nums2 的子集所以我们可以先遍历一遍 nums2并构造单调递增栈求出 nums2 中每个元素右侧下一个更大的元素。然后将其存储到哈希表中。然后再遍历一遍 nums1从哈希表中取出对应结果存放到答案数组中。这种解法的时间复杂度是 O(n)O(n)O(n)。
解题步骤 使用数组 ans 存放答案。使用 stack 表示单调递增栈。使用哈希表 d 用于存储 nums2 中下一个比当前元素大的数值映射关系为 当前元素值下一个比当前元素大的数值。 遍历数组 nums2对于当前元素 如果当前元素值较小则直接让当前元素值入栈。如果当前元素值较大则一直出栈直到当前元素值小于栈顶元素。 出栈时出栈元素是第一个大于当前元素值的元素。则将其映射到 d 中。 遍历完数组 nums2建立好所有元素下一个更大元素的映射关系之后再遍历数组 nums1。 从 d 中取出对应的值将其加入到答案数组中最终输出答案数组 ans。
代码
class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) - List[int]:stack[]ddict()ans[]for i in nums2:while stack and istack[-1]: d[stack[-1]]istack.pop()stack.append(i)for j in nums1:ans.append(d.get(j,-1))return ans类似的题目还有下一个更大元素 I I唯一不同的是数组是循环的。简单做法是将nums循环一次即numsnumsnums再求解后取结果的前m个数值作为答案
class Solution:def nextGreaterElements(self, nums: List[int]) - List[int]:mlen(nums)numsnumsnums nlen(nums)stack[]ans[-1]*nfor i in range(n):while stack and nums[i]nums[stack[-1]]:indexstack.pop()ans[index]nums[i]stack.append(i)return ans[:m]上面代码中 indexstack.pop()等同于
indexstack[-1]
stack.pop() 4.3 每日温度 739. 每日温度 - 力扣LeetCode 给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
1≤temperatures.length≤1051 \le temperatures.length \le 10^51≤temperatures.length≤105。30≤temperatures[i]≤10030 \le temperatures[i] \le 10030≤temperatures[i]≤100。
示例
输入: temperatures [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0]
解题思路 本题就是寻找每个元素右侧第一个更大的元素然后返回「该元素」与「右侧第一个比当前元素更大的元素」之间的距离将所有距离保存为数组返回结果。考虑使用「单调递增栈」栈中保存元素的下标。
详细步骤
将答案数组 ans 全部赋值为 0。然后遍历数组每个位置元素。如果栈为空则将当前元素的下标入栈。如果栈不为空且当前数字大于栈顶元素对应数字则栈顶元素出栈并计算下标差。此时当前元素就是栈顶元素的下一个更高值将其下标差存入答案数组 ans 中保存起来判断栈顶元素。直到当前数字小于或等于栈顶元素则停止出栈将当前元素下标入栈。最后输出答案数组 ans。
代码
class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:stack[]nlen(temperatures)ans[0]*nfor i in range(n):while stack and temperatures[i]temperatures[stack[-1]]:indexstack.pop()ans[index]i-indexstack.append(i)return ans4.4 股票价格跨度 0901. 股票价格跨度 设计一个算法收集某些股票的每日报价并返回该股票当日价格的跨度 。当日股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数从今天开始往回数包括今天。 实现 StockSpanner 类
StockSpanner() 初始化类对象。int next(int price) 给出今天的股价 price 返回该股票当日价格的 跨度 。
示例
输入 [100,80,60,70,60,75,85]输出那么股票跨度将是 [1,1,1,2,1,4,6] 。
解题思路
「求解小于或等于今天价格的最大连续日」等价于「求出左侧第一个比当前股票价格大的股票并计算距离」。求出左侧第一个比当前股票价格大的股票我们可以使用「单调递减栈」来做。
详细步骤 初始化方法初始化一个空栈即 self.stack [] 求解今天股票价格的跨度 初始化跨度 span 为 1。 如果今日股票价格 price 大于等于栈顶元素 self.stack[-1][0]则 将其弹出即 top self.stack.pop()。跨度累加上弹出栈顶元素的跨度即 span top[1]。继续判断直到遇到一个今日股票价格 price 小于栈顶元素的元素位置再将 [price, span] 压入栈中。 如果今日股票价格 price 小于栈顶元素 self.stack[-1][0]则直接将 [price, span] 压入栈中。 最后输出今天股票价格的跨度 span。
代码
class StockSpanner:def __init__(self):self.stack []def next(self, price: int) - int:span 1while self.stack and price self.stack[-1][0]:top self.stack.pop()span top[1]self.stack.append([price, span])return span也可以将遍历时每个元素的下标 self.cur存入栈中然后计算入栈时当前元素下标和入栈前栈顶元素的下标差就行
class StockSpanner:def __init__(self):#单调递增插入栈。左侧第一个更大的元素就是插入元素时的栈顶元素self.stack [(inf,-1)]self.cur-1 # 遍历时的当前元素下标赋值为-1第一次遍历时下标0def next(self, price: int) - int:self.cur1 # 第一个元素下标为0while self.stack and priceself.stack[-1][0]: self.stack.pop() self.stack.append([price,self.cur])# 当前元素已入栈所以其插入前的栈顶元素是stack[-2]return self.cur-self.stack[-2][1]4.5 去除重复字母 0316. 去除重复字母 这道题和1081. 不同字符的最小子序列是一样的。 给你一个字符串 s 请你去除字符串中重复的字母使得每个字母只出现一次。需保证 返回结果的字典序最小要求不能打乱其他字符的相对位置。
示例
输入s “cbacdcbc”输出“acdb”
解题思路
去重可以通过 「使用哈希表存储字母出现次数」 的方式将每个字母出现的次数统计起来再遍历一遍去除重复的字母。不能打乱其他字符顺序按顺序遍历将非重复的字母存储到答案数组或者栈中最后再拼接起来就能保证不打乱其他字符顺序。字典序最小意味着字典序小的字母应该尽可能放在前面。 对于第 i 个字符 s[i] 而言如果第 0 ~ i - 1 之间的某个字符 s[j] 在 s[i] 之后不再出现了那么 s[j] 必须放到 s[i] 之前。而如果 s[j] 在之后还会出现并且 s[j] 的字典序大于 s[i]我们则可以先舍弃 s[j]把 s[i] 尽可能的放到前面。后边再考虑使用 s[j] 所对应的字符。
要满足第 3 条需求我们可以使用 「单调递减栈」 来解决即使用单调栈存储 s[i] 之前出现的非重复、并且字典序最小的字符序列。整个算法步骤如下
先遍历一遍字符串用哈希表 d 统计出每个字母出现的次数。然后使用单调递减栈保存当前字符之前出现的非重复、并且字典序最小的字符序列。当遍历到 s[i] 时如果 s[i] 没有在栈中出现过 比较 s[i] 和栈顶元素 stack[-1] 的字典序。如果 s[i] 的字典序小于栈顶元素 stack[-1]并且栈顶元素次数 1则将栈顶元素弹出并从哈希表 d 中减去栈顶元素出现的次数继续遍历。直到栈顶元素出现次数为 1 时停止弹出。此时将 s[i] 添加到单调栈中。 如果 遍历时s[i] 在栈中出现过就将其次数-1因为我们只在s[i] 首次遍历时将其入栈后续重复时不入栈其统计次数应该-1。最后将单调栈中的字符依次拼接为答案字符串并返回。
class Solution:def removeDuplicateLetters(self, s: str) - str:from collections import Counterddict(Counter(s))# 使用单调递减栈保证字典序最小# 如果遍历的当前元素小于栈顶元素当其次数大于1时将栈顶弹出对应次数-1。直至0时不再弹出stack[]for ch in s:if ch not in stack:while stack and chstack[-1] and d[stack[-1]]1:# 注意这里是先统计次数再执行pop操作并且是chstack[-1]d[stack[-1]]-1stack.pop() stack.append(ch)# 如果ch已经在栈中将其次数-1等同于之前的相同元素会出栈当前重复元素入栈。# 否则[bbcaac]这种会出错。else: d[ch]-1return .join(stack)4.6 柱状图中最大的矩形 0084. 柱状图中最大的矩形 给定一个非负整数数组 heights heights[i] 用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。要求计算出在该柱状图中能够勾勒出来的矩形的最大面积。
示例
输入heights [2,1,5,6,2,3]输出10解释最大的矩形为图中红色区域面积为 10
解题思路 暴力枚举「宽度」 一重循环枚举所有柱子第二重循环遍历柱子右侧的柱子所得的宽度就是两根柱子形成区间的宽度高度就是这段区间中的最小高度。然后计算出对应面积记录并更新最大面积。这样下来时间复杂度为 O(n2)O(n^2)O(n2)。 暴力枚举枚举「高度」。一重循环枚举所有柱子以柱子高度为当前矩形高度然后向两侧延伸遇到小于当前矩形高度的情况就停止。然后计算当前矩形面积记录并更新最大面积。这样下来时间复杂度也是 O(n2)O(n^2)O(n2)。 单调栈遍历求左右边界 当前柱子heights[i]所能延伸到的最大面积S[i]其实就是左右两侧高度不小于heights[i]的最远柱子之间的面积。也就是说柱子i往左右延伸直到碰到的柱子高度heights[i]时停止。所以本题关键是求数组heights中每个元素左侧最近的更小值和右侧最近的更小值考虑使用单调递减栈求解。注意面积延伸时碰到更小的高度才停止所以使用严格单调递减栈遍历的元素严格大于栈顶元素才入栈小于等于栈顶元素时栈顶弹出。所以判断条件是heights[i]heights[stack[-1]]有等号。
class Solution:def largestRectangleArea(self, heights: List[int]) - int:stack[]nlen(heights)# 寻找左侧更小值使用单调递减插入栈栈中只存入栈元素的下标。# 当前元素≤栈顶元素时栈顶弹出。# 直到当前元素入栈此时栈顶元素就是当前元素的左侧第一个更小值。# 如果碰到空栈说明左侧没有更小的元素将其下标记为-1哨兵表示往左可以延伸到数组开头left[-1]*n for i in range(n):while stack and heights[i]heights[stack[-1]]:stack.pop() left[i]stack[-1] if stack else -1stack.append(i)# print(left)right[n]*nstack[] # 没有重新设置stack初始化坑# 寻找右侧更小值使用单调递减弹出栈# 当前元素≤栈顶元素时将栈顶弹出。此时弹出前的栈顶元素的右侧第一个更小值就是当前元素# 如果为空栈说明右侧没有更小元素将其下标记为n也就是往右遍历到数组结尾for i in range(n):while stack and heights[i]heights[stack[-1]]: right[stack[-1]]i if stack else nstack.pop() stack.append(i)# print(right) ans [(right[i]-left[i]-1) * heights[i] for i in range(n)] return max(ans)上面的代码中我们用插入栈得到左侧更小的元素使用弹出栈得到右侧更小的元素但都使用了单调递减栈判断条件也相同所以其实可以一次遍历得到左右边界优化后代码为
class Solution:def largestRectangleArea(self, heights: List[int]) - int:stack[]nlen(heights)left[-1]*n right[n]*n for i in range(n):while stack and heights[i]heights[stack[-1]]:right[stack[-1]]i stack.pop() left[i]stack[-1] if stack else -1stack.append(i)ans [(right[i]-left[i]-1) * heights[i] for i in range(n)] if n 0 else 0return max(ans)4.7 接雨水 0042. 接雨水 给定n个非负整数组成的数组 height 其表示表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 nheight.lengthn height.lengthnheight.length。1≤n≤2∗1041 \le n \le 2 * 10^41≤n≤2∗104。0≤height[i]≤1050 \le height[i] \le 10^50≤height[i]≤105。
解题思路 求出蓄水边界 最明显的某个柱子左右有更高的柱子时这个柱子上才可以接雨水 这样需要首先求出数组中每个元素左侧和右侧最近的更高柱子即蓄水的左右边界。所以考虑使用单调递增栈求出左右边界的下标。比如height [0,1,0,2,1,0,1,3,2,1,2,1]时左边界left[-1, -1, 1, -1, 3, 4, 3, -1, 7, 8, 7, 10]右边界right[1, 3, 3, 7, 7, 6, 7, 12, 12, 10, 12, 12]寻找左右边界时因为是寻找两侧严格大的柱子判断条件不一样没办法一次遍历出来可以自行测试。 求出蓄水面积 蓄水宽度左右边界下标差蓄水高度min左右边界高度- 当前柱子高度。这样可以算出每个柱子可以接的雨水。还是以上面例子为例此时得到的结果ans柱子下标i接水面积area[(2,1),(4,3),(5,1),(6,3),(9,1)]。可见计算的结果都是对的唯一错误是下标4和6的这两个柱子蓄水面积都计算了一次。观察可以发现这两个柱子的左右边界完全相同其结果只需要计算一次考虑使用字典d存储每个柱子的边界。对于相同的边界蓄水面积只计算一次。
class Solution:def trap(self, height: List[int]) - int:#寻找左边界nlen(height)stack[]# 构造单调递增栈更小的元素才入栈。例如[8,3,3,7.7,9]当第一个3入栈时7才是右侧更大的元素所以是当前元素严格大于栈顶元素才入栈left,right[-1]*n,[n]*nfor i in range(n):while stack and height[i]height[stack[-1]]:right[stack[-1]]i stack.pop() #left[i]stack[-1] if stack else -1stack.append(i)stack[] # 构造单调递增栈更小的元素才入栈。例如[8,3,3]当第二个3入栈时8才是左侧更大的元素# 所以判断条件中有等号相同元素也要弹出。for i in range(n):while stack and height[i]height[stack[-1]]:stack.pop()left[i]stack[-1] if stack else -1stack.append(i)print(left:,left)print(right:,right)# 如果碰到左右边界完全一样只计算一次ans[]ddict()for i in range(n):# 遍历每个元素的左右边界l,rleft[i],right[i]if l!-1 and r!n: if (l,r) not in d: # 相同边界的柱子蓄水量只计算一次area(min(height[l],height[r])-height[i])*(right[i]-left[i]-1)ans.append(area)#print(i,area)d[(l,r)]ireturn sum(ans)优化一一次遍历出左右边界 上面代码可以优化其实无论是height[i]height[stack[-1]]还是height[i]height[stack[-1]]只用一个判断条件得到的结果有一个边界是不完全准确的但是不影响最终结果。比如
height[i]height[stack[-1]]时左边界不准为left [-1, -1, 1, -1, 3, 4, 4(3), -1, 7, 8, 8(7), 10]右边界是准的right [1, 3, 3, 7, 7, 6, 7, 12, 12, 10, 12, 12]。上面第6个柱子左边界应该是3这里判断是4。结果就是计算时左边界4和柱子6的高度一样area0。所以虽然不是严格的左边界但是不影响最终结果。以上面数组为例area[(2,1),(4,3),(5,1),(6,0),(9,1)]
class Solution:def trap(self, height: List[int]) - int:#寻找左右边界nlen(height)stack[]# 构造单调递增栈更小的元素才入栈。例如[8,3,3,7.7,9]当第一个3入栈时7才是右侧更大的元素所以是当前元素严格大于栈顶元素才入栈# 例如[8,3,3]当第二个3入栈时8才是左侧更大的元素left,right[-1]*n,[n]*nfor i in range(n):while stack and height[i]height[stack[-1]]: # 这里可以是≥right[stack[-1]]i stack.pop() left[i]stack[-1] if stack else -1stack.append(i)# print(left:,left)# print(right:,right)ans[] for i in range(n):# 遍历每个元素的左右边界l,rleft[i],right[i]if l!-1 and r!n: area(min(height[l],height[r])-height[i])*(right[i]-left[i]-1)ans.append(area)# print(i,area)return sum(ans)优化二在一次遍历中求左右边界并同时求出蓄水面积 这里需要将判断条件左右边界不为数组头尾if l!-1 and r!n: 改为if stack因为只有遇到空栈才说明左右侧没有更高的柱子。
class Solution:def trap(self, height: List[int]) - int:ans 0stack []size len(height)for i in range(size):# 这里写成height[i] height[stack[-1]]也是没有问题的while stack and height[i] height[stack[-1]]:cur stack.pop(-1)# 当前元素被弹出时其上一个元素是左侧更大值将要入栈的是右侧更大值if stack:left stack[-1] right i high min(height[i], height[stack[-1]]) - height[cur]ans high * (right - left - 1)else: # 遇到空栈停止弹出跳出循环breakstack.append(i)return ans 4.8 最大矩形 0085最大矩阵 参考题解《Python3 前缀和单调栈计算最大矩形》 给定一个仅包含 0 和 1 大小为 rows x cols 的二维二进制矩阵找出只包含 1 的最大矩形并返回其面积。 示例 输入matrix [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出6 解释最大矩形如下图所示。
解题思路 我们可以统计每一行中每个元素上方“1”的个数这样就等同于得到了每一行柱子的高度height。 对于height的计算根据最大前缀和思想当前位置j为‘0’则height[j]0当前位置为‘1’则需要加上上一层连续1的个数即height[j]1。例如本题中height[2][3, 1, 3, 2, 2] 用0084. 柱状图中最大的矩形中同样的做法求得柱状图的最大面积就行。例如示例中第二行面积为[3, 5, 3, 6, 2] 遍历每一行得到各行的最大面积取全局最大值就行。 class Solution:def maximalRectangle(self, matrix: List[List[str]]) - int:m,nlen(matrix),len(matrix[0])height[0]*n # 每行上方1的个数可视作柱子的高度ans[] # 存储每行的最大面积for i in range(m):for j in range(n):# 第m行每个位置含1的高度height[j]height[j]1 if matrix[i][j]1 else 0#根据柱子高度计算最大面积等同于第84题stack[]left,right[-1]*n,[n]*nfor h in range(n):while stack and height[h]height[stack[-1]]:right[stack[-1]]hstack.pop()left[h]stack[-1] if stack else -1stack.append(h)res[(right[h]-left[h]-1)*height[h] for h in range(n)] ans.append(max(res))return max(ans)
