win7如何建设免费网站,四川政务网官网入口,盘锦网站建设流程,网站服务器租用有什么好原题链接#x1f517;#xff1a;最小栈 难度#xff1a;中等⭐️⭐️
题目
设计一个支持 push #xff0c;pop #xff0c;top 操作#xff0c;并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推…原题链接最小栈 难度中等⭐️⭐️
题目
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
示例 1:
输入 [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]]
输出 [null,null,null,null,-3,null,0,-2]
解释 MinStack minStack new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); -- 返回 -3. minStack.pop(); minStack.top(); -- 返回 0. minStack.getMin(); -- 返回 -2.
提示
-231 val 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次
最小栈
最小栈是一种特殊的栈数据结构它在普通的栈功能基础上增加了一个额外的功能能够在常数时间内返回当前栈的最小元素。最小栈通常用于那些需要频繁查询当前最小值的场景比如在遍历数组或列表时找到所有子数组的最小值。
最小栈的实现一般有两种方法 辅助栈使用一个辅助栈来存储当前栈中元素的最小值。每次压栈操作时将当前元素与辅助栈的栈顶元素进行比较并将较小的值压入辅助栈。这样辅助栈的栈顶元素始终是当前栈中所有元素的最小值。 排序数组在每次压栈操作后将新元素插入到一个数组中并保持数组的有序性。这样数组的第一个元素就是当前栈的最小值。这种方法的时间复杂度较高因为插入操作可能需要O(n)的时间。
最小栈的典型操作包括
push(x)将元素x压入栈中。pop()弹出栈顶元素。top()返回栈顶元素。getMin()返回当前栈的最小元素。
最小栈在实现上需要考虑空间和时间效率通常辅助栈的方法在时间效率上更有优势。
题解
解题思路 LeetCode 上的 “最小栈”Min Stack问题要求设计一个特殊的栈它在进行常规栈操作的同时还需要支持在常数时间内获取栈的最小元素。 问题描述 设计一个支持 push、pop 和 top 操作的栈并且在常数时间内能够获取到栈的最小元素。 解题思路 使用两个栈创建两个栈一个用于存储所有元素mainStack另一个用于存储当前的最小元素minStack。初始化minStack 初始化为空。Push 操作 将元素压入 mainStack。检查 minStack 是否为空或者新元素小于等于 minStack 的栈顶元素。如果是将该元素也压入 minStack。 Pop 操作 弹出 mainStack 的栈顶元素。如果该元素等于 minStack 的栈顶元素那么 minStack 也弹出栈顶元素。 Top 操作 返回 mainStack 的栈顶元素。 GetMin 操作 返回 minStack 的栈顶元素即当前最小元素。 c demo
#include iostream
#include stackclass MinStack {
private:std::stackint stack;std::stackint minStack;public:/** initialize your data structure here. */MinStack() {}void push(int x) {stack.push(x);if (minStack.empty() || x minStack.top()) {minStack.push(x);}}void pop() {if (!stack.empty()) {int topElement stack.top();stack.pop();if (topElement minStack.top()) {minStack.pop();}}}int top() {if (!stack.empty()) {return stack.top();}throw std::runtime_error(Stack is empty);}int getMin() {if (!minStack.empty()) {return minStack.top();}throw std::runtime_error(Stack is empty);}
};int main() {MinStack minStack;minStack.push(-2);minStack.push(0);minStack.push(-3);std::cout Minimum: minStack.getMin() std::endl; // 返回 -3minStack.pop();std::cout Top: minStack.top() std::endl; // 返回 0std::cout Minimum: minStack.getMin() std::endl; // 返回 -2return 0;
}输出结果 Minimum: -3 Top: 0 Minimum: -2 代码仓库地址getMin
