欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

荐 Leetcode_栈与队列

程序员文章站 2022-06-06 21:03:00
225. 用队列实现栈链接:https://leetcode-cn.com/problems/implement-stack-using-queues/solution/225-yong-dui-lie-shi-xian-zhan-by-liucx-3/使用队列实现栈的下列操作:push(x) – 元素 x 入栈pop() – 移除栈顶元素top() – 获取栈顶元素empty() – 返回栈是否为空解题思路栈:洗盘子,脏盘子放最上面(尾部进),洗盘子也从最上面开始(尾部出),简称后进先出...

225. 用队列实现栈


链接:https://leetcode-cn.com/problems/implement-stack-using-queues/solution/225-yong-dui-lie-shi-xian-zhan-by-liucx-3/

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

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

解题思路

栈:洗盘子,脏盘子放最上面(尾部进),洗盘子也从最上面开始(尾部出),简称后进先出LIFO(last in first out)
队列:排队打饭先来后到,先排的(尾部进),先打到饭(头部出),简称先进先出FIFO(first in first out)

栈的顶:最先插入的元素
队的顶:最后插入的元素

deque()是双端队列,与list不同的在于deque可以对首尾进行删除操作(pop与leftpop)
因为使用队列实现栈,所以只能使用leftpop删除头

用栈表示队列:T232
荐
                                                        Leetcode_栈与队列

代码

class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 = deque()
        self.stack2 = deque()

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.stack1.append(x)

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        while len(self.stack1) > 1:
            self.stack2.append(self.stack1.popleft())
        tmp = self.stack1.popleft()
        self.stack1,self.stack2 = self.stack2,self.stack1
        return tmp


    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        while len(self.stack1) > 0:
            tmp = self.stack1.popleft()
            self.stack2.append(tmp)
        self.stack1,self.stack2 = self.stack2,self.stack1
        return tmp


    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        if len(self.stack1) == 0 and len(self.stack2) == 0:
            return True
        else:
            return False




# 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()

232. 用栈实现队列


链接:https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/232-yong-zhan-shi-xian-dui-lie-by-liucx-3/

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

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

解题思路

栈:洗盘子,脏盘子放最上面(尾部进),洗盘子也从最上面开始(尾部出),简称后进先出LIFO(last in first out)
队列:排队打饭先来后到,先排的(尾部进),先打到饭(头部出),简称先进先出FIFO(first in first out)

栈的顶:最先插入的元素
队的顶:最后插入的元素
pop() 函数用于移除列表中的一个元素(默认最后一个元素),并且返回该元素的值。
因为使用栈表示队列,所以只能用pop移除最后端元素。

用队列实现栈:T225
荐
                                                        Leetcode_栈与队列

代码

class MyQueue(object):

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


    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.queue1.append(x)


    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if self.queue2 == []:
            while len(self.queue1) != 0:
                self.queue2.append(self.queue1.pop())
        return self.queue2.pop()



    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.queue2 == []:
            while len(self.queue1) != 0:
                self.queue2.append(self.queue1.pop())
        return  self.queue2[-1]


    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        if self.queue1 == [] and self.queue2 == []:
            return True
        else:
            return False



# 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()

155. 最小栈


链接:https://leetcode-cn.com/problems/min-stack

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

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

解题思路

  • 在入栈操作时,加入一个辅助栈用来存放最小值。
  • 在出栈操作是,需要把辅助栈的最后一位也删除掉
  • 时间复杂度:O(1),每步的操作都只有O(1)的复杂度
  • 空间复杂度:O(N),一共插入n个元素入栈。

代码

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minstack = [float('inf')]


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        self.minstack.append(min(x,self.minstack[-1]))


    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        self.minstack.pop()
         
    def top(self):
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.minstack[-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()

20. 有效的括号


链接:https://leetcode-cn.com/problems/valid-parentheses

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

  1. 左,右括号必须匹配。"[)" False
  2. 左括号必须以正确的顺序闭合。"[(]" False
  3. 空字符串是有效字符串。

解题思路

  • 判断字符串是否有效的策略是本题难点:
    1. 最内层的括号一定是匹配的,匹配可删除,不匹配直接False
    2. 删掉最内层后,倒数第二层括号也是匹配的,不匹配输出False。依次内推。
    3. 最内层也就是最后的输入,最先进行计算,Last input First output(LIFO),使用栈进行处理。
  • 时间复杂度:O(n),一次只对一个字符进行push或pop操作,一共n个
  • 空间复杂度:O(n),最对可能要使用len(s)=n的长度

代码

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        mapping = {"]":"[" , ")":"(","}":"{" } #用字典对括号进行匹配
        stack = []
        for x in s:
            if x not in mapping: #左括号则push
                stack.append(x)
            else: #右括号
                if not stack: # 如“]”,False
                    return False
                if mapping[x] == stack[-1]: #最顶层括号匹配了
                    stack.pop()
                else:
                    return False
        return not stack # not stack:stack为空输出True,否则False

739. 每日温度


链接:https://leetcode-cn.com/problems/daily-temperatures/

列表T保存n天的每日气温,输出列表result,保存比每日温度出现下一次更高温的间隔天数。没有输出0。

example:

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

解题思路

  • 单调栈或队列的使用:最左或最右与当前数字相比较的题目。
  • 用stack保存天数,即temperatures的下标。reslut作为结果保存间隔天数。
  • 当前温度T[i]小于前一个温度T[stack[-1]]时,当前天数i入栈
  • 当前温度T[i]大于前一个温度T[stack[-1]]时,stack[-1]出栈,输出需要等待的天数i-tmp_index,结果保存在result[tmp_index]。
    • 用while循环,因为要与stack栈中入栈过的都进行对比。
  • 时间复杂度:O(n),遍历n个天数
  • 空间复杂度:O(n),栈最多用n个空间,result最多用n个空间

代码

class Solution(object):
    def dailyTemperatures(self, T):
        stack = []
        result = [0]*len(T)
        for i in range(len(T)):
            while stack and T[i]>T[stack[-1]]:
                tmp_index = stack.pop()
                result[tmp_index] = i - tmp_index
            stack.append(i)
        return result

503. 下一个更大元素 II


链接:https://leetcode-cn.com/problems/next-greater-element-ii/

一个循环数组,输出下一个比当前数字大的数字。

example:

输入: [1,2,1]
输出: [2,-1,2]

解题思路

  • 本题同T739,多了一个循环,再遍历一次数组即可。
  • 时间复杂度:O(2n),最长两次遍历
  • 空间复杂度:O(n)

代码

class Solution(object):
    def nextGreaterElements(self, nums):
        n = len(nums)
        stack = []
        result = [-1]*n
        if not nums:
            return []
        for i in range(n):
            while stack and nums[i]>nums[stack[-1]]:
                last_index = stack.pop()
                result[last_index] = nums[i]
            stack.append(i)
        
        for i in range(n):
            while nums[i]>nums[stack[-1]]:
                last_index = stack.pop()
                result[last_index] = nums[i]
        return result

循环数组的第二种表达方式

  • 用i%n取余来遍历两遍数组。
  • 时空复杂度没区别,只是代码简化了

代码

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        stack = []
        result = [-1]*n
        for i in range(n*2):
            while stack and nums[i%n]>nums[stack[-1]]:
                last_index = stack.pop()
                result[last_index] = nums[i%n]
            stack.append(i%n)
        return result

本文地址:https://blog.csdn.net/weixin_43427585/article/details/107347855