Skip to content
Gallery
Algoschool
Algocircle
Share
Explore
Level 1

icon picker
Stack problems

func isValid(s string) bool {
stack := make([]byte, 0)
for i := range s {
if isOpen(s[i]) {
stack = append(stack, s[i])
} else {
if len(stack) == 0 {
return false
}

pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]

if getPair(pop) != s[i] {
return false
}
}
}

return len(stack) == 0
}

// "{{})"

func isOpen(char byte) bool {
open := map[byte]bool{
'{':true,
'(':true,
'[':true,
}
return open[char]
}

func getPair(char byte) byte {
open := map[byte]byte{
'{':'}',
'(':')',
'[':']',
}
return open[char]
}

⁠
https://leetcode.com/problems/sliding-window-maximum/
⁠
⁠
"""
6
----
5
3


"""

class MaxStack:
def __init__(self):
self.s = []
self.max = []
def push(self, v):
if len(self.max) == 0:
self.max.append(v)
else:
newMax = self.max[-1]
if v > newMax:
newMax = v
self.max.append(newMax)
self.s.append(v)
def pop(self):
self.max.pop()
return self.s.pop()

def getMax(self):
return float('-inf') if not self.max else self.max[-1]

class MaxQueue:
def __init__(self):
self.a = MaxStack()
self.b = MaxStack()

def enqueue(self, v):
self.a.push(v)

def dequeue(self):
if not self.b.s:
while self.a.s:
self.b.push(self.a.pop())
return self.b.pop()

def getMax(self):
return max(self.a.getMax(), self.b.getMax())
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
# 1 2 3
maxQueue = MaxQueue()
for i in range(k):
maxQueue.enqueue(nums[i])

res.append(maxQueue.getMax())
for i in range(k, len(nums)):
maxQueue.enqueue(nums[i])
maxQueue.dequeue()
res.append(maxQueue.getMax())

return res
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.