- 浏览: 171736 次
- 性别:
- 来自: 济南
文章分类
最新评论
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
实现一个可以返回最小值的堆栈,因为题目要求我们在O(1)的时间复杂度下返回最小值,我们需要用一个堆栈minStack单独来维护最小值,当进行push操作的时候,我们要检查压栈的元素是否是最小值,如果是最小值还要把这个元素放到minStack中去。pop操作的时候要检查出栈的元素是否为最小值,如果为最小值,在minStack中也要将这个元素弹出,getMin操作的时候只需要返回minStack的顶端的元素就可以了,期间不要忘记检查堆栈是否为空。代码如下:
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
实现一个可以返回最小值的堆栈,因为题目要求我们在O(1)的时间复杂度下返回最小值,我们需要用一个堆栈minStack单独来维护最小值,当进行push操作的时候,我们要检查压栈的元素是否是最小值,如果是最小值还要把这个元素放到minStack中去。pop操作的时候要检查出栈的元素是否为最小值,如果为最小值,在minStack中也要将这个元素弹出,getMin操作的时候只需要返回minStack的顶端的元素就可以了,期间不要忘记检查堆栈是否为空。代码如下:
class MinStack { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> minStack = new Stack<Integer>(); public void push(int x) { stack.push(x); if(!minStack.isEmpty()) { if(x <= minStack.peek()) { minStack.push(x); } } else { minStack.push(x); } } public void pop() { if(stack.isEmpty()) return; int num = stack.pop(); if(num == minStack.peek()) { minStack.pop(); } } public int top() { if(stack.isEmpty()) return Integer.MAX_VALUE; return stack.peek(); } public int getMin() { if(minStack.isEmpty()) return Integer.MAX_VALUE; return minStack.peek(); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 221Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 219You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 336Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 325Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 443Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 498Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 423Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 611Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 420The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 378Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 511Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 521Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 364All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 853Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 876Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 547Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 592Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 757Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 724You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 623For a undirected graph with tre ...
相关推荐
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -...
其次,如果推送的元素低于minStack的top元素,则将其推送到minStack,否则我们将克隆minStack的top元素。 当我们弹出一个元素时,我们会同时从两个堆栈中弹出它,以使两个堆栈保持同步。 这样,我们总是可以通过弹...
Minstackos生活 不推荐使用的tc,切换到debian
剑指Offer(Python多种思路实现):包含min函数的栈 ...class MinStack: def __init__(self): self._stack = [] def push(self, x: int) -> None: cur_min = self.getMin() if x None: self._stac
栈, 最小值
代码type MinStack struct {a []int//存储元素b []int //辅助栈 维护栈的最小值/* initialize your dat
设计包含最小函数min(),取出元素函数pop(),加入元素函数push()的栈MinStack,实现其中指定的方法(2)。 MinStack中数据存储使用Java原生的Stack,存储数据元素为int。请实现以下对应的方法,完善功能。 ...
以155.Min Stack2为例: . └── 155.Min Stack2 #LeetCode第150题 ├── JavaScript / TypeScript for LeetCode (五十九).md #存放此题博客文档 ├── 155.Min Stack2.js #存放此题JavaScript Solution └─...
Min Stack Valid Parentheses Longest Valid Parentheses Largest Rectangle in Histogram Evaluate Reverse Polish Notation Implement Stack using Queues 队列 Implement Queue using Stacks 二叉树 二叉树的遍历...
* [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap](https://github.com/kamyu104/LeetCode#heap) * [Tree]...
minStack stack 111 二叉树的最小深度 , tree 110 平衡二叉树 tree 104 二叉树的最大深度 tree 100 相同的树 tree 94 二叉树的中序遍历 tree 70 爬楼梯 dp 53 最大子序和 dp 26 删除排序数组中的重复项 array 1 两数...
笔试题 包括 -> - python基础知识: numpy,分位数。 - 算法: 找出两个字符串的最长公共子串。...- 简单程序设计: Minstack类实现。 - 数据库: MySQL, 获取点击数前三的USERID。 - 浏览器打开网址经历了哪些过程。
在任何给定的时间点,minStack 将保持最小元素直到现在(推送或弹出值) 满足条件的线性搜索或二分搜索,因为解决方案始终存在 由于其他方法为大输入提供 TLE,因此筛选埃托色尼 按位解决方案,因为二的幂只包含 1 ...
leetcode添加元素使和等于 Algorithm With Python 算法的python实现 [TOC] 1.Stack 栈 介绍 栈允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);...MinStack 1_002 最小栈(LeerCode 115) 2.lin
Stack 11 Diameter of Binary Tree 12 Last Stone Weight 13 Contiguous Array 14 Perform String Shifts 日 问题描述 问题和解决方案链接 Git 解决方案页面 15 Product of Array Except Self 16 Valid Parenthesis ...
Stack Easy 394 字符串编码 Decode String Medium 链表 No Problem Solution Difficulty Tag 2 两数相加 Add Two Numbers Medium 19 删除链表倒数第N个节点 Remove Nth Node From End of List Medium 21 合并两个...
gridstack.js是一款响应式可拖拽的元素组件网格布局jQuery插件。该jQuery插件允许你创建给予Bootstarp v3的响应式可拖拽的网格布局界面,可以用于制作可拖拽的多列网格布局。并且它还可以支持触摸屏设备。
155.Min Stack 设置一个辅助栈专门用于放置当前最小的值,每次压栈时主栈压入新数据,辅助栈压入当前最小数据 316.Remove 重要 单调栈的问题,栈内元素大致递增,记录下串内字符的数量。有四题大致相同,总结一下...
(min stack), 3.5 (two stack queue) 重要。两道题面M被问到过。3.6 (sort stack)感觉也有可能被考到。 第四章 (4.1, 4.3, 4.5 Leetcode上有): 感觉4.2, 4.3, 4.5,4.6, 4.7 重要。4.5 (valid BST)面E,Q碰到...
Min Stack 完成LeetCode 232. Implement Queue using Stacks Week5 完成LeetCode 147. Insertion Sort List 完成作业Quick sort Week6 10/11 国庆弹性放假 Week7 完成作业Heap sort Week8 完成作业Merge sort Week9 ...