Публичное собеседование по LeetCode 05.09

gistfile1.txt

# hi! I'm here!

Sliding Window Maximum, k = 3

```
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
 ```

# 8:14 - 8:28 -> 14 min: discussion
# 8:29 - 9:10 -> 40 min

# T = O(len(nums)), 
# T_worse push = O(k)

StackElement = namedtuple("StackElement", "element,stack_max")

class MaxStack:
  def __init__(self):
    self.data = []
  
  def size(self):
    return len(self.data)
  
  def push(self, v):
    if not self.data:
      self.data.append(StackElement(element=v, stack_max=v))
    else:
      new_max = max(self.data[-1].stack_max, v)
      self.data.append(StackElement(element=v, stack_max=new_max))
  
  def pop(self):
    return self.data.pop().element
  
  def max(self):
    return self.data[-1].stack_max

  
class MaxQueue:
  def __init__(self):
    self.l_stack = MaxStack()
    self.r_stack = MaxStack()
    
  def size(self):
    return self.l_stack.size() + self.r_stack.size()
  
  def max(self):
    if self.l_stack.size() and self.r_stack_size():
      return max(self.l_stack.max(), self.r_stack.max())
    
    if self.r_stack_size():
      return self.r_stack.max()
    
    if self.l_stack.size():
      return max(self.l_stack.max()
    
  
  def push(self, v):
    self.r_stack.push(v)
                 
  def pop(self):
    if not self.l_stack.size():
      while self.r_stack.size():
        self.l_stack.push(self.r_stack.pop())
    return self.l_stack.pop()
                 

# k = 3
# [1  3  -1] -3  5  3  6  7
                 
def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
  window_max = []  # 3 3 5 
  max_queue = MaxQueue()
  
  for v in nums:
    if max_queue.size() == k:
      window_max.append(max_queue.max())
    max_queue.push(v)
    if max_queue.size() > k:
      max_queue.pop()

  window_max.append(max_queue.max())
                 
  return window_max