用栈实现队列

力扣地址

题目描述

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

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

示例:

1
2
3
4
5
6
7
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 操作）。

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.myList = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.myList.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        return self.myList.pop(0)

    def peek(self) -> int:
        """
        Get the front element.
        """
        return self.myList[0]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.myList) == 0

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.myList = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.myList.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        return self.myList.pop(0)

    def peek(self) -> int:
        """
        Get the front element.
        """
        return self.myList[0]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.myList) == 0

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

用队列实现栈

力扣地址

题目描述

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

  • push(x) — 元素 x 入栈
  • pop() — 移除栈顶元素
  • top() — 获取栈顶元素
  • empty() — 返回栈是否为空

注意:

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

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.myList = []

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.myList.append(x)

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.myList.pop()

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.myList[-1]

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.myList) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        int cnt = queue.size();
        while (cnt-- > 1) {
            queue.add(queue.poll());
        }
    }

    public int pop() {
        return queue.remove();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

最小值

力扣地址

题目描述

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.myList = []
        self.minList = []

    def push(self, x: int) -> None:
        self.myList.append(x)
        if not self.minList or x <= self.minList[-1]:
            self.minList.append(x)

    def pop(self) -> None:
        if self.myList[-1] == self.minList[-1]:
            self.minList.pop()
        self.myList.pop()

    def top(self) -> int:
        return self.myList[-1]

    def getMin(self) -> int:
        return self.minList[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    private int min;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        dataStack.add(x);
        min = Math.min(min, x);
        minStack.add(min);
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
        min = minStack.isEmpty() ? Integer.MAX_VALUE : minStack.peek();
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

有效的括号

力扣地址

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

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

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for char in s:
            if char == '(' or char == '[' or char == '{':
                stack.append(char)
            else:
                if len(stack) == 0:
                    return False
                cStack = stack.pop()
                b1 = char == ')' and cStack != '('
                b2 = char == ']' and cStack != '['
                b3 = char == '}' and cStack != '{'
                if b1 or b2 or b3:
                    return False

        return len(stack) == 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char cStack = stack.pop();
            boolean b1 = c == ')' && cStack != '(';
            boolean b2 = c == ']' && cStack != '[';
            boolean b3 = c == '}' && cStack != '{';
            if (b1 || b2 || b3) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

每日温度

力扣地址

题目描述

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

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

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

题目解答

在每次遍历数组元素时，将其推入栈，判断当前遍历元素是否比栈顶元素大

1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import List


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = []
        dist = [0] * len(T)
        for i in range(len(T)):
            while len(stack) != 0 and T[i] > T[stack[-1]]:
                preIndex = stack.pop()
                dist[preIndex] = i - preIndex
            stack.append(i)
        return dist
1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] dist = new int[n];
    Stack<Integer> indexs = new Stack<>();
    for (int curIndex = 0; curIndex < n; curIndex++) {
        while (!indexs.isEmpty() && temperatures[curIndex] > temperatures[indexs.peek()]) {
            int preIndex = indexs.pop();
            dist[preIndex] = curIndex - preIndex;
        }
        indexs.add(curIndex);
    }
    return dist;
}

下一个更大元素Ⅱ

力扣地址

题目描述

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

示例 1:

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

题目解答

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        nums2 = nums * 2
        stack = []
        rlt = [-1] * len(nums2)
        for i in range(len(nums2)):
            while len(stack) != 0 and nums2[i] > nums2[stack[-1]]:
                preIndex = stack.pop()
                rlt[preIndex] = nums2[i]
            stack.append(i)
        return rlt[:len(nums)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] next = new int[n];
    Arrays.fill(next, -1);
    Stack<Integer> pre = new Stack<>();
    for (int i = 0; i < n * 2; i++) {
        int num = nums[i % n];
        while (!pre.isEmpty() && nums[pre.peek()] < num) {
            next[pre.pop()] = num;
        }
        if (i < n){
            pre.push(i);
        }
    }
    return next;
}