Solutions to JZ 6, JZ 9, & JZ 30 (same as LeetCode 155 Min Stack).
JZ 6
Return an array of the linked list (Easy) [link]
Push values into the stack and pop out of the stack. Time complexity O(n), space complexity O(n).
class Solution:
def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
stack = []
while listNode:
if listNode == None:
break
stack.append(listNode.val)
listNode = listNode.next
stack.reverse() # or stack[::-1]
return stack
JZ 9
Use two stacks to implement a queue (Easy). [link]
Time complexity of push is O(1). Time complexity of pop is O(n). Space complexity in total is O(n).
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
if not self.stack1 and not self.stack2:
return -1
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
JZ 30 | LeetCode 155
Stack with min() function (Easy). [NowCoder link] [LeetCode link]
This problem requires time complexity of min() is O(1), so we need an additional stack to help. push() is used to append x to stack 1, and if stack2 is empty or x is a smaller value, also append x to stack 2, so stack 2 stores values in descending order. pop() is used to pop out the final value of stack 1, and if the final value of stack 1 and 2 is consistent, also pop out the final value of stack 2. top() pops out stack 1. min() pops out the final value of stack2 , i.e. returns the min value of stack 1.
class Solution:
def __init__(self):
self.stack1, self.stack2 = [], []
def push(self, x: int) -> None:
self.stack1.append(x)
if not self.stack2 or self.stack2[-1] >= x:
self.stack2.append(x)
def pop(self) -> None:
v = self.stack1.pop()
if v == self.stack2[-1]:
self.stack2.pop()
def top(self) -> int:
return self.stack1[-1]
def min(self) -> int:
return self.stack2[-1]
