MinStack minStack = new MinStack();

时间: 2023-05-21 08:02:55 浏览: 33
这是一个关于数据结构的问题,MinStack 是一个栈,它可以在常数时间内获取栈中的最小值。这个问题需要使用 Java 编程语言来实现。以下是一个示例代码: ``` class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x) { stack.push(x); if (minStack.isEmpty() || x <= minStack.peek()) { minStack.push(x); } } public void pop() { if (stack.peek().equals(minStack.peek())) { minStack.pop(); } stack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } } ``` 这个 MinStack 类有 push、pop、top 和 getMin 四个方法,它们的时间复杂度都是 O(1)。其中,push 方法会将元素 x 压入栈中,并且如果 x 是当前栈中的最小值,就将它压入 minStack 中;pop 方法会将栈顶元素弹出,并且如果栈顶元素是当前最小值,就将它从 minStack 中弹出;top 方法返回栈顶元素;getMin 方法返回当前栈中的最小值。

相关推荐

以下是使用stack方式隨機生成長寬的程式: python import random def generate_rectangles(num_rectangles, min_len, max_len, min_width, max_width): """ Generate a list of rectangles with random lengths and widths. Parameters: num_rectangles (int): the number of rectangles to generate min_len (int): the minimum rectangle length max_len (int): the maximum rectangle length min_width (int): the minimum rectangle width max_width (int): the maximum rectangle width Returns: list: a list of randomly generated rectangles, where each rectangle is represented as a tuple (length, width) """ rectangles = [] stack = [] for i in range(num_rectangles): # generate random length and width length = random.randint(min_len, max_len) width = random.randint(min_width, max_width) rectangle = (length, width) # add rectangle to the stack if not stack: stack.append(rectangle) else: top = stack[-1] if rectangle[0] == top[0]: stack.append(rectangle) else: # pop rectangles with smaller width from the stack and update their height while stack and rectangle[0] < stack[-1][0]: prev_rect = stack.pop() height = prev_rect[1] + (rectangle[0] - prev_rect[0]) * prev_rect[1] // prev_rect[0] rectangles.append((prev_rect[0], height)) if not stack: stack.append(rectangle) else: # calculate height of new rectangle height = top[1] + (rectangle[0] - top[0]) * top[1] // top[0] stack.append((rectangle[0], height)) # pop remaining rectangles from the stack and update their height while stack: prev_rect = stack.pop() if not stack: height = prev_rect[1] else: top = stack[-1] height = prev_rect[1] + (top[0] - prev_rect[0]) * top[1] // prev_rect[0] rectangles.append((prev_rect[0], height)) return rectangles 使用方法與上一個程式相同,只需調整參數 min_len, max_len, min_width, max_width 即可。例如: python rectangles = generate_rectangles(10, 1, 10, 1, 10) print(rectangles) 輸出結果如下(每個元素都是一個 tuple,分別表示長和寬): [(1, 4), (4, 4), (1, 8), (5, 7), (3, 3), (3, 9), (10, 9), (2, 2), (6, 2), (10, 3)]

data segment string1 db 'please input score: $' string2 db 'output score : $' string3 db '| max score | $' string4 db '| min score | $' string5 db '| Passers-by | $' string6 db '| Not Passer-by | $' string7 db '| Average score | $' string8 db '+----------------+-------+$' kong db ' $' string9 db ' | $' string0 db 'Press any key to continue...$' pas dw 0000H npa dw 0000H avg dw 0000H num dw 0000H avg2 dw 0000H score dw 60 dup(0) data ends stack segment dw 64 dup(0) stack ends code segment assume cs:code,ds:data,ss:stack main proc far start: t: call ready call input call sort call count call output jmp t main endp ;========================ready============================= ready: mov ax,data mov ds,ax ;ds数据段寄存器 mov ax,stack mov ss,ax ;ss站段寄存器 mov dx,offset string1 mov ah,09h int 21h xor bx,bx ;临时存放输入进来的数 xor cx,cx ; xor si,si ;score的指针 xor di,di ;计数 ret ;==========================input========================== input: mov ah,1 int 21h cmp al,0dh jz over cmp al,20h jz save sub al,30h mov cl,4 shl bx,cl add bl,al jmp input save: mov score[si],bx add si,2 inc di xor bx,bx jmp input over: mov score[si],bx inc di mov dl,0ah mov ah,02h int 21h mov cx,di dec cx xor bx,bx ret ;===========================sort========================= sort: ;bx=0,用冒泡排序,bx为要改变的哪一位的坐标 mov si,2 mov dx,cx cmp2: mov ax,score[bx] cmp ax,score[bx+si] jnc cmp3 ;大于或相等时转 xchg ax,score[bx+si] mov score[bx],ax cmp3: add si,2 dec dx jnz cmp2 add bx,2 ; loop sort mov dx,offset string2 mov ah,09h int 21h sub si,si 注释这段代码

Tarjan算法是一种基于深度优先搜索的强连通分量(SCC)算法。它可以用于在有向图中找到所有的强连通分量。 以下是一个使用Matlab实现Tarjan算法的示例: matlab function SCC = tarjanAlgorithm(adjMatrix) n = size(adjMatrix, 1); % 获取图的顶点数 index = 1; % 初始化索引 indices = zeros(n, 1); % 顶点的访问索引 lowlinks = zeros(n, 1); % 顶点的最低访问索引 onStack = false(n, 1); % 记录顶点是否在栈中 stack = []; % 存储顶点的栈 SCC = {}; % 存储强连通分量 function strongconnect(v) indices(v) = index; % 设置顶点的访问索引 lowlinks(v) = index; % 设置顶点的最低访问索引 index = index + 1; stack = [stack, v]; % 将顶点压入栈中 onStack(v) = true; % 对v的邻接顶点进行递归处理 for w = 1:n if adjMatrix(v, w) == 1 % 如果v和w之间有边 if indices(w) == 0 % 如果w还未被访问过 strongconnect(w); lowlinks(v) = min(lowlinks(v), lowlinks(w)); % 更新v的最低访问索引 elseif onStack(w) % 如果w在栈中 lowlinks(v) = min(lowlinks(v), indices(w)); % 更新v的最低访问索引 end end end % 如果v是一个强连通分量的根节点 if lowlinks(v) == indices(v) scc = []; w = -1; while w ~= v w = stack(end); stack = stack(1:end-1); onStack(w) = false; scc = [scc, w]; end SCC{end+1} = scc; end end % 对每个未访问过的顶点进行处理 for v = 1:n if indices(v) == 0 strongconnect(v); end end end 这是一个递归实现的Tarjan算法。你可以将邻接矩阵作为输入参数传递给tarjanAlgorithm函数,并且它将返回一个包含所有强连通分量的单元格数组SCC。 希望这个示例能帮助到你!如果有任何问题,请随时提问。
可以使用 Tarjan 算法来寻找图中的所有最小环。以下是使用 Python 实现 Tarjan 算法的示例代码: python def tarjan(edges): n = len(edges) index = [0] * n lowlink = [0] * n onstack = [False] * n stack = [] result = [] def strongconnect(node, i): index[node] = i lowlink[node] = i i += 1 stack.append(node) onstack[node] = True for next_node in edges[node]: if index[next_node] == 0: i = strongconnect(next_node, i) lowlink[node] = min(lowlink[node], lowlink[next_node]) elif onstack[next_node]: lowlink[node] = min(lowlink[node], index[next_node]) if lowlink[node] == index[node]: cycle = [] while True: top = stack.pop() onstack[top] = False cycle.append(top) if top == node: break result.append(cycle) return i for node in range(n): if index[node] == 0: i = strongconnect(node, 1) return result 在以上代码中,我们使用 index 和 lowlink 两个列表来维护每个节点的索引和 lowlink 值。onstack 列表用于记录节点是否在栈中。stack 列表记录当前 DFS 的节点栈。result 列表用于存储找到的所有环。 在 strongconnect 函数中,我们首先将当前节点入栈,并将其标记为在栈中。然后对于当前节点的每个邻居节点,如果邻居节点还没有被访问过,则递归调用 strongconnect 函数。在递归调用结束后,我们更新当前节点的 lowlink 值。如果邻居节点在栈中,则说明我们找到了一个环,更新当前节点的 lowlink 值。如果当前节点的 lowlink 值等于其索引值,则说明当前节点是环的根节点,将栈中的节点弹出并添加到 result 中。 最后,我们遍历所有节点,对于每个未访问过的节点,调用 strongconnect 函数。函数返回 result 列表,其中包含所有的最小环。 示例代码的运行结果为: [[3, 4], [8, 9]] 说明图中有两个最小环,包含节点 {3, 4} 和 {8, 9}。

最新推荐

Java结构型设计模式资料day03

本课程从设计模式的一些相关的概念开始,再到软件设计原则,重点讲解23种设计模式,针对每一种模式都配备了相关的代码。最后通过一个综合案例将常用的设计模式使用起来。 市面上已经有很多的设计模式的教程,而我们这套课程有哪儿些特色呢? 从基础开始。只要你有JavaSE的基础都可以学习 全面。针对设计模式及其模式的变形及开发中是如何使用的 案例经典。学习spring框架是最好的提升的途径,spring框架将面向对象体现的淋漓尽致 本课程从设计模式的一些相关的概念开始,再到软件设计原则,重点讲解23种设计模式,针对每一种模式都配备了相关的代码。最后通过一个综合案例将常用的设计模式使用起来。 市面上已经有很多的设计模式的教程,而我们这套课程有哪儿些特色呢? 从基础开始。只要你有JavaSE的基础都可以学习 全面。针对设计模式及其模式的变形及开发中是如何使用的 案例经典。学习spring框架是最好的提升的途径,spring框架将面向对象体现的淋漓尽致

高项十大过程组,49个管理过程,定义作用总结

高项十大过程组,49个管理过程,定义作用总结。

云盘产品的赠送式联合会员:核心指标解读.docx

云盘产品的赠送式联合会员:核心指标解读.docx

代码随想录最新第三版-最强八股文

这份PDF就是最强⼋股⽂! 1. C++ C++基础、C++ STL、C++泛型编程、C++11新特性、《Effective STL》 2. Java Java基础、Java内存模型、Java面向对象、Java集合体系、接口、Lambda表达式、类加载机制、内部类、代理类、Java并发、JVM、Java后端编译、Spring 3. Go defer底层原理、goroutine、select实现机制 4. 算法学习 数组、链表、回溯算法、贪心算法、动态规划、二叉树、排序算法、数据结构 5. 计算机基础 操作系统、数据库、计算机网络、设计模式、Linux、计算机系统 6. 前端学习 浏览器、JavaScript、CSS、HTML、React、VUE 7. 面经分享 字节、美团Java面、百度、京东、暑期实习...... 8. 编程常识 9. 问答精华 10.总结与经验分享 ......

基于交叉模态对应的可见-红外人脸识别及其表现评估

12046通过调整学习:基于交叉模态对应的可见-红外人脸识别Hyunjong Park*Sanghoon Lee*Junghyup Lee Bumsub Ham†延世大学电气与电子工程学院https://cvlab.yonsei.ac.kr/projects/LbA摘要我们解决的问题,可见光红外人重新识别(VI-reID),即,检索一组人的图像,由可见光或红外摄像机,在交叉模态设置。VI-reID中的两个主要挑战是跨人图像的类内变化,以及可见光和红外图像之间的跨模态假设人图像被粗略地对准,先前的方法尝试学习在不同模态上是有区别的和可概括的粗略的图像或刚性的部分级人表示然而,通常由现成的对象检测器裁剪的人物图像不一定是良好对准的,这分散了辨别性人物表示学习。在本文中,我们介绍了一种新的特征学习框架,以统一的方式解决这些问题。为此,我们建议利用密集的对应关系之间的跨模态的人的形象,年龄。这允许解决像素级中�

javascript 中字符串 变量

在 JavaScript 中,字符串变量可以通过以下方式进行定义和赋值: ```javascript // 使用单引号定义字符串变量 var str1 = 'Hello, world!'; // 使用双引号定义字符串变量 var str2 = "Hello, world!"; // 可以使用反斜杠转义特殊字符 var str3 = "It's a \"nice\" day."; // 可以使用模板字符串,使用反引号定义 var str4 = `Hello, ${name}!`; // 可以使用 String() 函数进行类型转换 var str5 = String(123); //

数据结构1800试题.pdf

你还在苦苦寻找数据结构的题目吗?这里刚刚上传了一份数据结构共1800道试题,轻松解决期末挂科的难题。不信?你下载看看,这里是纯题目,你下载了再来私信我答案。按数据结构教材分章节,每一章节都有选择题、或有判断题、填空题、算法设计题及应用题,题型丰富多样,共五种类型题目。本学期已过去一半,相信你数据结构叶已经学得差不多了,是时候拿题来练练手了,如果你考研,更需要这份1800道题来巩固自己的基础及攻克重点难点。现在下载,不早不晚,越往后拖,越到后面,你身边的人就越卷,甚至卷得达到你无法想象的程度。我也是曾经遇到过这样的人,学习,练题,就要趁现在,不然到时你都不知道要刷数据结构题好还是高数、工数、大英,或是算法题?学完理论要及时巩固知识内容才是王道!记住!!!下载了来要答案(v:zywcv1220)。

通用跨域检索的泛化能力

12056通用跨域检索:跨类和跨域的泛化2* Soka Soka酒店,Soka-马上预订;1印度理工学院,Kharagpur,2印度科学学院,班加罗尔soumava2016@gmail.com,{titird,somabiswas} @ iisc.ac.in摘要在这项工作中,我们第一次解决了通用跨域检索的问题,其中测试数据可以属于在训练过程中看不到的类或域。由于动态增加的类别数量和对每个可能的域的训练的实际约束,这需要大量的数据,所以对看不见的类别和域的泛化是重要的。为了实现这一目标,我们提出了SnMpNet(语义Neighbourhood和混合预测网络),它包括两个新的损失,以占在测试过程中遇到的看不见的类和域。具体来说,我们引入了一种新的语义邻域损失,以弥合可见和不可见类之间的知识差距,并确保潜在的空间嵌入的不可见类是语义上有意义的,相对于其相邻的类。我们还在图像级以及数据的语义级引入了基于混�

css怎么写隐藏下拉列表

您可以使用 CSS 中的 display 属性来隐藏下拉列表。具体方法是: 1. 首先,在 HTML 中找到您想要隐藏的下拉列表元素的选择器。例如,如果您的下拉列表元素是一个 select 标签,则可以使用以下选择器:`select { }` 2. 在该选择器中添加 CSS 属性:`display: none;`,即可将该下拉列表元素隐藏起来。 例如,以下是一个隐藏下拉列表的 CSS 代码示例: ```css select { display: none; } ``` 请注意,这将隐藏所有的 select 元素。如果您只想隐藏特定的下拉列表,请使用该下拉列表的选择器来替代 sel

TFT屏幕-ILI9486数据手册带命令标签版.pdf

ILI9486手册 官方手册 ILI9486 is a 262,144-color single-chip SoC driver for a-Si TFT liquid crystal display with resolution of 320RGBx480 dots, comprising a 960-channel source driver, a 480-channel gate driver, 345,600bytes GRAM for graphic data of 320RGBx480 dots, and power supply circuit. The ILI9486 supports parallel CPU 8-/9-/16-/18-bit data bus interface and 3-/4-line serial peripheral interfaces (SPI). The ILI9486 is also compliant with RGB (16-/18-bit) data bus for video image display. For high speed serial interface, the ILI9486 also provides one data and clock lane and supports up to 500Mbps on MIPI DSI link. And also support MDDI interface.