滑动窗口的最大值问题

2019 年 10 月 3 日
筆記

????????????????????????

# ??? 2, 6, 1, 5, 3, 9, 7, 4  # ????? 4    [2,  6,  1,  5], 3,  9,  7,  4    => 6   2, [6,  1,  5,  3], 9,  7,  4    => 6   2,  6, [1,  5,  3,  9], 7,  4    => 9   2,  6,  1, [5,  3,  9,  7], 4    => 9   2,  6,  1,  5, [3,  9,  7,  4]   => 9    # ????? [6, 6, 9, 9, 9]

???????????? O(n)?

????

???????????????????????????????????????????????????????????????????? pop(), push(), max() ?? O(1) ??????????????????????????????????????????? O(n) ??????????????????

pop() ? push() ?? O(1) ????max() ????????????????????????????????????????????????????????????????——???????????????????????????????????????????????????????????????????????????????????????????????????????????? pop(), push(), max() ?? O(1) ?????? 2, 7, 4 ????????????????????? 2, 7, 7???????????????????????????????? O(1) ?????????? max?

????????????????????????? push?????? pop??????????? max() ? O(1) ????????? max() ? O(1) ????

?????????????????????????????? O(1) ??????????????????????????????????????????????????????? O(1) ???????????????????????????????????????????? O(1) ??????????????????

??? 2, 6, 1, 5, 3, 9, 7, 4 ????????????? 4????????? stack_out???????? stack_in???????????????? 4 ????

stack_out:      stack_in:                   (5, 6)         <- Top     None          (1, 6)                   (6, 6)                   (2, 2)         <- Bottom

?? (value, max) ?????????? value ???????? max???????? stack_in ?????????????????????

?????????? 2 ???? 3 ???

stack_out:      stack_in:                                  <- Top    (6, 6)    (1, 5)    (5, 5)          (3, 3)        <- Bottom

???????????????????????????? 3 ???? stack_out ?? 1 ???? stack_in ???????? O(1) ???? stack_out ??? 3 ???????????????? O(1) ???? stack_in ??????????????? stack_out ? stack_in ????????????????????????????????????????????????????? O(1) + O(1) + O(1) = O(1) ????????????????? O(1) ????? stack_out ?????????????? stack_in ?????????????????????????????????

???????????????????

?????

???????????? pop(), push(), max() ?? O(1) ????????????? pop() ???????? O(1)?????????????????????????????

1) ??????? stack_out ?????????? stack_out ?????????
2) ??????? stack_out ????????????????? stack_in ????????? stack_out ????????????????

???? 1) ? O(1) ?????? 2) ? O(m) ??? m ?????????????????????????????? pop() ???? O(1) ????????????????? O(n) ??

???????? stack_out ?????? 2??????? O(m) ?????????????????????????? O(nm)????????????????????? 2 ?????????????????? O(1) ????????????????????????????????????????? 2 ?????????? m ?????? stack_out ??????????? 2????? stack_in ?? m ?????? stack_out ????????????“????”?????????“??”????????? m ???? O(1) ????????????? m ???????? O(2) ?????????????????????????????????? O(2)??????? O(1) ??????? pop() ?????????? O(1) ????????????? O(n)???????????????????——????????????????????????????????????????????????????????????????????????????????

???????????????????????????????????????????????????????????????????????????? stack_in ?????????? stack_out ????????????? O(1) ??????????? O(4n) ??????????????????????? O(n)?

P.S.
?????????????????????????? Python ????????????????? append???? push?????? Python ???????????????

from typing import List  from collections import namedtuple    Node = namedtuple('Node', ['value', 'max'])      class MaxQueue():        def __init__(self, stack_len: int) -> None:          self.stack_in = []          self.stack_out = []          self.stack_len = stack_len        def pop(self) -> int:          if not self.stack_out:              if not self.stack_in:                  raise IndexError('pop from an empty queue')              else:                  self._move_in_to_out()          return self.stack_out.pop().value        def append(self, value: int) -> None:          if len(self.stack_in) >= self.stack_len:              if self.stack_out:                  raise IndexError('the queue is full')              else:                  self._move_in_to_out()          self._push_to_stack(self.stack_in, value)        def max(self) -> int:          if self.stack_in and self.stack_out:              return max(self.stack_in[-1].max, self.stack_out[-1].max)          if self.stack_in:              return self.stack_in[-1].max          if self.stack_out:              return self.stack_out[-1].max        def _move_in_to_out(self) -> None:          while self.stack_in:              self._push_to_stack(self.stack_out,                                  self.stack_in.pop().value)        def _push_to_stack(self, stack: List[Node], value: int) -> None:          if stack:              stack.append(Node(value, max=max(value, stack[-1].max)))          else:              stack.append(Node(value, max=value))