栈的压入，弹出序列
题目要求
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
用例输入
示例 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 之前弹出。
提示
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
做题思路
我们来分别遍历这两个数组，遍历的同时先将pushed数组压入栈中，然后我们判断栈顶的数据是否跟popped数组的数据相等，如果相等就出栈，popped数组的下标+1，不相等我们就继续将pushed数组中的数据压入栈中，循环中这个数组，最后如果栈中为空则说明popped序列是pushed数组的弹出序列，不为空则不是。
此时栈顶的数据等于popped[j]，所以我们弹出栈顶的数据，并且将j++；
栈顶数据等于popped[j]，继续弹出。
继续该操作
栈里面为空，所以我们返回true。
代码实现
C语言代码实现
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){ int* arr = (int*)malloc(pushedSize*sizeof(int)); int tail = 0; int j = 0; for(int i = 0; i<pushedSize; i++) { arr[tail] = pushed[i]; while(j<poppedSize && tail>=0 && arr[tail] == popped[j]) { tail--; j++; } tail++; } return tail==0; }
Java代码实现
class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { Stack<Integer> stack = new Stack<>(); int j = 0; for(int i = 0; i<pushed.length; i++) { stack.push(pushed[i]); while( j<popped.length && !stack.empty() && stack.peek().equals(popped[j])) { stack.pop(); j++; } } return stack.empty(); } }
最小栈
题目要求
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
这是一幕提供的接口
class MinStack { public MinStack() { } public void push(int val) { } public void pop() { } public int top() { } public int getMin() { } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.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 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
做题思路
这个题目需要我们使用两个栈，一个栈用来放所有整数，一个的栈顶存放的是最小的整数，叫做最小栈。当我们入栈的时候，当第一次入栈的时候因为最小栈里面是空的，所以我们直接将数据压入栈中，后来入最小栈的时候，我们就需要判断需要入栈的这个数据是否小于最小栈栈顶的数据，如果小于或等于就入栈，否则不入栈。当我们出栈的时候我们还需要对最小栈做出变化，当我们出栈的这个数等于最小栈的栈顶的数据，我们也将最小栈栈顶的数据弹出。后面的返回栈顶的数据，跟栈中的最小值我就不多叙述了。
重复此操作
然后我们在弹出三次栈
弹出的7不等于MinStack栈顶的-1
-1等于MinStack栈顶的-1，所以MinStack也需要弹出
代码实现
因为这道题用C语言实现较复杂，所以我们这个题就直接用Java来实现。
Java代码实现
class MinStack { private Stack<Integer> stack; private Stack<Integer> minstack; public MinStack() { stack = new Stack<>(); minstack = new Stack<>(); } public void push(int val) { stack.push(val); if(minstack.empty()) { minstack.push(val); } else { if(val <= minstack.peek()) { minstack.push(val); } } } public void pop() { //判断栈是否为空 if(!stack.empty()) { 这里我们用Integer防止取出的数据不在-128~127之间 Integer val = stack.peek(); stack.pop(); if(val.equals(minstack.peek())) { minstack.pop(); } } } public int top() { if(!stack.empty()) { return stack.peek(); } return -1; } public int getMin() { if(!minstack.empty()) { return minstack.peek(); } return -1; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
