首页 > leetcode-155 最小栈

leetcode-155 最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索栈中的最小元素。

示例：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

方法一：使用辅助栈

使用辅助栈来存储当前数据栈的最小元素，即插入元素时 同时维护数据栈和辅助栈，数据栈正常放入元素；辅助栈的栈顶则保存当前数据栈中最小的元素即可

实现如下：

class MinStack { 
public:/** initialize your data structure here. */MinStack() { }void push(int x) { data.push(x);//维护辅助栈//如果当前元素大小 小于辅助栈顶元素，则将当前元素放入辅助栈中if (min_stack.empty()) { min_stack.push(x);} else { if (x < min_stack.top()) { min_stack.push(x);} else { min_stack.push(min_stack.top());}}}void pop() { data.pop();min_stack.pop();}int top() { return data.top();}int getMin() { return min_stack.top();}
private:stack<int> min_stack;stack<int> data;
};

方法二：不用辅助栈

插入元素时同时，两个为一个单元，第二个为栈最小元素，第一个为要插入的元素

实现如下:

class MinStack { 
public:/** initialize your data structure here. */MinStack() { }void push(int x) { if(data.empty()){ data.push(x);data.push(x);} else { if (x >= data.top()) { int tmp = data.top();data.push(x);data.push(tmp);} else { data.push(x);data.push(x);}}}void pop() { data.pop();data.pop();}//返回时需先保存栈顶的最小元素int top() { int tmp = data.top();data.pop();int result = data.top();data.push(tmp);return result;}int getMin() { return data.top();}
private:stack<int> data;
};

更多相关：

  • C++ Stack Queue priority_queue

    栈stack：stack 后入先出（LIFO） q.top()获取栈顶元素（并不删除）q.pop()删除栈顶元素q.push(x)向栈中加入元素q.empty()判断栈是否为空 队列queue：先入先出（FIFO）   q.front()获取队首元素（并不删除）q.pop()删除队首元素q.push(x)向队列中加入元素q....

  • c++ resizereserve

    resize()，设置大小（size）; reserve()，设置容量（capacity）; size()是分配容器的内存大小，而capacity()只是设置容器容量大小，但并没有真正分配内存。 打个比方：正在建造的一辆公交车，车里面可以设置40个座椅（reserve(40);），这是它的容量，但并不是说它里面就有了40个座椅，只能说...

  • 用v-for循环动态定位坐标显示元素，并遍历元素的left和top坐标位置（只需要用到元素的宽高、索引、每行显示数量）

    v-for="(index,$i) in total" :key="$i":style="{left:`${itemWidth*((index-1)%rowItemCount)}px`,top:`${itemHeight*(Math.ceil(index/rowItemCount)-1)}px`}" //total是显示总数量 //l...

  • 几种经典的居中技巧（垂直和水平居中）

      技巧一（推荐指数★★★★★） 采用top、right、bottom、left，可以不在乎父元素的宽度和高度，对GPU损耗低于技巧三，但是对浏览器内存的消耗高于技巧三 .子元素 {/*父元素需要position: relative|absolute;*/position: absolute;margin: auto;to...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • C++的STL栈实现获取栈中最小元素的成员

    实现一个获取栈中最小数据成员的函数，该栈支持如下操作： 1.push(x) : 将元素x压入栈中 2.pop() : 弹出(移除)栈顶元素 3.top() : 返回栈顶元素 4.getMin() : 返回栈内最小元素 要求时间复杂度为O(1) 这里关键是如何获取最小值，栈中的元素不断增加，且要达到O（1）常数级的时间复杂度，即创建好...

©2024 11GX.COM