各位朋友们，大家好，今天是我leedcode刷题的第五篇，我们一起来看看吧。

栈的压入，弹出序列

leetcode之栈的压入与弹出序列（难度：中等）

题目要求

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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();}
}

最小栈

leetcode之最小栈（难度：中等）

题目要求

设计一个支持 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();*/