leetcode | 栈和队列

微信扫一扫,分享到朋友圈

leetcode | 栈和队列

232. 用栈实现队列 (简单)

使用栈实现队列的下列操作:

  • push(x) — 将一个元素放入队列的尾部。
  • pop() — 从队列首部移除元素。
  • peek() — 返回队列首部的元素。
  • empty() — 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

  • 你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

解答:

用两个栈结构:push 和 pop

  • 入队:进 push 栈
  • 出队:
    若 pop 为空,push 栈里面的数依次倒进 pop, pop栈顶弹出
    若 pop 不为空, pop栈顶弹出

JAVA代码:

class MyQueue {
private Stack<Integer> push;
private Stack<Integer> pop;
/** Initialize your data structure here. */
public MyQueue() {
push = new Stack<Integer>();
pop = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
push.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (pop.empty()){
while (!push.empty()){
pop.push(push.pop());
}
}
return pop.pop();
}
/** Get the front element. */
public int peek() {
if (pop.empty()){
while (!push.empty()){
pop.push(push.pop());
}
}
return pop.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
if (push.empty() && pop.empty()){
return true;
}
else return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
  • 入队

时间复杂度:O(1)

空间复杂度:O(n)

  • 出队

摊还时间复杂度:O(1)

空间复杂度:O(1)

225. 用队列实现栈 (简单)

使用队列实现栈的下列操作:

  • push(x) — 将元素 x 推入栈中。
  • pop() — 删除栈顶的元素。
  • top() — 获取栈顶元素。
  • empty() — 返回栈是否为空

注意:

  • 你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
  • 你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

题解:

用两个队列实现栈结构。

队列:先进先出

栈:先进后出

使用两个队列:data 和 help

出栈:

  1. data 中除最后一个数,其余数依次入队列 help。
  2. data中唯一的一个数出队.
  3. data 和 help地址互换

入栈:直接入队列 data.

JAVA代码:

class MyStack {
private Queue<Integer> data;
private Queue<Integer> help;
/** Initialize your data structure here. */
public MyStack() {
data = new LinkedList<Integer>();
help = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
data.add(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
while (data.size()>1){
help.add(data.remove());
}
int top = data.remove();
Queue<Integer> temp = data;
data = help;
help = temp;
return top;
}
/** Get the top element. */
public int top() {
while (data.size()>1){
help.add(data.remove());
}
int top = data.peek();
help.add(data.remove());
Queue<Integer> temp = data;
data = help;
help = temp;
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {
if (data.isEmpty()){
return true;
}
else return false;
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/

时间复杂度:入队O(1), 出队O(n)

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.

解答:

设计两个栈:data 和 min

data 代表当前栈,min 保存当前栈的最小元素。

进栈时:比较当前元素 x 与 min 栈顶元素 top

  1. 若 x < top, 那么 x 同时进 min 栈
  2. 若 x>=top, 那么数值 top 进 min 栈

出栈时:data 和 min 同时弹出栈顶元素。

mini 的栈顶元素即为 data 栈中的最小元素。

JAVA代码

class MinStack {
/** initialize your data structure here. */
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MinStack() {
stackData = new Stack<Integer>();
stackMin = new Stack<Integer>();
}
public void push(int x) {
stackData.push(x);
if (!stackMin.isEmpty()) {
if (x < stackMin.peek()) {
stackMin.push(x);
}
else stackMin.push(stackMin.peek());
}
else{
stackMin.push(x);
}
}
public void pop() {
stackData.pop();
stackMin.pop();
}
public int top() {
return stackData.peek();
}
public int getMin() {
return stackMin.peek();
}
}

时间复杂度:O(1)

空间复杂度:O(n)

20. 有效的括号 (简单)

给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i=0; i<s.length(); i++){
if (!stack.isEmpty() && ((stack.peek() == '('&& s.charAt(i)==')')||(stack.peek() == '{'&& s.charAt(i)=='}')||(stack.peek() == '['&& s.charAt(i)==']')))
stack.pop();
else stack.push(s.charAt(i));
}
return stack.isEmpty()? true: false;
}
}

时间复杂度O(n)

空间复杂度O(n)

739. 每日温度* (中等)

根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表
temperatures = [73, 74, 75, 71, 69, 72, 76, 73],
你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

题解:

1. 暴力法

每一个元素都往后找第一个比它大的数的下标

//暴力算法
// 每一个元素都往后找比他大的数
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
for(int i = 0; i<T.length; i++){
for (int j = i; j<T.length; j++){
if (T[j]>T[i]){
res[i] = j-i;
break;
}
}
}
return res;
}
}

时间复杂度O(n^2)

空间复杂度O(n), 存结果

2. 用一个next数组存每个元素的下标*

从后向前遍历元素,在next中找下标为比当前元素大的元素,next中值最小的元素即为离当前元素最近的比它的元素。

class Solution {
public int[] dailyTemperatures(int[] T) {
int[] next = new int[101];
Arrays.fill(next, Integer.MAX_VALUE);
int[] res = new int[T.length];
for (int i=T.length-1; i>=0; i--){
int curr = Integer.MAX_VALUE;   //在next中当前元素值, 即比T[i]大的元素的下标
//在next数组中找比当前元素大且离当前元素最近的元素,得到其下标
for (int j = T[i]+1; j<101; j++){
if (next[j] < curr){
curr = next[j];
}
}
if (curr<Integer.MAX_VALUE)
res[i] = curr-i;
next[T[i]] = i;
}
return res;
}
}

时间复杂度O(nw), w为元素取值的范围宽度

空间复杂度O(n+w)

3. 利用栈*

栈中存放元素下标。

倒序遍历数组,若当前元素比栈中下标对应元素大,出栈,直到当前元素小于栈中小标对应的元素。那么栈中就是需要找到的下标。

//栈
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
Stack<Integer> stack = new Stack<>();
for (int i = T.length-1; i>=0; i--){
while (!stack.isEmpty() && T[i]>=T[stack.peek()]){
stack.pop();
}
if (!stack.isEmpty())
res[i] = stack.peek()-i;
stack.push(i);
}
return res;
}
}

时间复杂度O(n)

空间复杂度O(n)

503. 下一个更大元素 II

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数;
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。

注意: 输入数组的长度不会超过 10000。

题解:利用栈

与739题类似,不同的是这题给出的数组为循环数组。

对循环数组的访问可用以下形式: i % nums.length
, i
为任意数字。

而对于这题,我们只需要重复访问数组两次,所以i的取值为 0~2*nums.length-1

可以理解为数组中的每一个数字,希望能访问到它后面的数字,也能访问到它前面的数字。

class Solution {
public int[] nextGreaterElements(int[] nums) {
int size = nums.length;
int[] res = new int[size];
Stack<Integer> stack = new Stack<>();
for (int i = 2*size-1; i>=0; i--){
while (!stack.isEmpty() && nums[i%size] >= nums[stack.peek()]){
stack.pop();
}
res[i%size] = stack.isEmpty()? -1: nums[stack.peek()];
stack.push(i%size);
}
return res;
}
}

时间复杂度O(n)

空间复杂度O(n)

微信扫一扫,分享到朋友圈

leetcode | 栈和队列

Apache ActiveMQ远程代码执行漏洞 (CVE-2020-11998) 通告

上一篇

你想了解的分布式文件系统HDFS,看这一篇就够了

下一篇

你也可能喜欢

leetcode | 栈和队列

长按储存图像,分享给朋友