Skip to content
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]
}
"""
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.
This is not the way.
Try clicking the ··· in the right corner or using a keyboard shortcut (
CtrlP
) instead.