理解滑动窗口
2019-12-14 本文已影响0人
胖胖胖胖啊
记录一下自己对滑窗的理解。
滑窗所解决的问题，如206. Minimum Size Subarray Sum，抽象出来后是二维空间极值的问题。其本质还是一个搜索问题，关键是搜索策略的制定。
下面白板上l和r代表的是窗口的左右两端的索引，F代表状态无效，T代表状态有效，暴力解的情况下，需要搜索检测所有的状态空间，复杂度为O(N^2)
sliding window
利用滑窗，能将复杂度降低到O(N)。 其本质上来源于单调性，一般可以理解为，随着左端点位置的增加，其最优决策的右端点位置单调不减。即设F(l)表示l对应的最优决策位置，F(l)单调不减。 注意到上图，随着l的增加，最优决策位置r是单调不减的。有了这些性质，就可以制定类似于240. Search a 2d Matrix-ii的搜索策略，即l和r都只沿同一个方向进行移动。上图中红色标记的方格表示使用滑窗时，检测的状态。
F(0) = 3
F(1) = 4
F(2) = 5
F(3) = 7
F(4) = 7
...
而862. Shortest Subarray with Sum at Least K看似是一道滑窗题，但却并没有类似的决策单调性，考虑如下简单的test case,有F(0) = 2， F(1) = 1, 即F并不满足单调不减，如果使用滑窗的话，会导致错过一些可能是解的状态, 比如下面的test case会错过 l = 1, r = 1的状态, 从而导致错误的答案。
arr = [-3, 2, 6], k = 1
